$POJ1995$ $Raising$ $Modulo$ $Numbers$

链接

背景

这题其实是 (a^wedge b) ， (AcWing89/CH0101) 的原版， (ACM-ICPC) (Czech) (Technical) (University) (Open) (Contest) (1999) (D)题， (POJ1995) 。

题意

给定 (T) 组数据。每次给定一个模数 (p) ，然后给出 (h) 组数 (a_i,b_i) ，求(sum_limits{i in [1,h]}{a_i^{b_i}} mod p)的值。

解法

对于每组数据，套用快速幂模板即可。
时间复杂度是 (O(Thlog_n)) 的。

代码

$View$ $Code$

//省略头文件
using namespace std;
inline int read()
{
	int ret=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		ret=(ret<<1)+(ret<<3)+ch-'0';
		ch=getchar();
	}
	return ret*f;
}
inline long long qpow(long long a,long long b,long long mod)
{
	long long ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
int a,b,p,h,z,ans;
int main()
{
	z=read();
	for(register int i=1;i<=z;i++)
	{
		ans=0;
		p=read();
		h=read();
		for(register int j=1;j<=h;j++)
		{
			a=read();
			b=read();
			ans=(ans+qpow(a,b,p))%p;
		}
		printf("%d
",ans);
	}
	return 0;
}