【题解】POJ P1995【Raising Modulo Numbers】

这是我第二次交POJ的题,rank从150,000瞬间飙到120,000+,真是玄学哇

这里是在《算法竞赛进阶指南》里面看到的题,刚开这本书,好难(我太弱了(学长:难你可以跳着看哇))。

【题意】给出p,再给出n组a,b的值,求\sum_{i = 1}^{n}a_{i}^{b_{i}} mod p的值

真·二进制快速幂

#include<cstdio>

typedef long long int64;

int64 binaryPow(int64 a,int64 b,int64 p){
	int64 ans = 1 % p;
	
	for(;b;b >>= 1){
		if(b & 1){
			ans = ans * a % p;
		}
		a = a * a % p;
	}
	return ans;
}

int main(){
	int T;
	scanf("%d",&T);
	
	while(T--){
		int64 p,h;
		scanf("%lld %lld",&p,&h);
		
		int64 ans = 0;
		while(h--){
			int64 a,b;
			scanf("%lld %lld",&a,&b);
			ans += binaryPow(a,b,p);
		}
		ans %= p;
		printf("%lld\n",ans);
	}
	
	return 0;
}