PKU 1995-Raising Modulo Numbers

問題概要

H,Mが与えられる。
Σ(i=1..H)Ai^BiをMod Mで求めよ

解法

繰り返し二乗法を使う

実装(C++)

#include <cstdio>
using namespace std;
int Z,M,H,a,b;
typedef long long lli;
lli mod_pow(lli a,lli b){
	if(b==0)return 1;
	lli res=mod_pow((a*a)%M,b/2);
	if(b%2)res=(res*a)%M;
	return res;
}
int main() {
	for(scanf("%d",&Z);Z--;){
		scanf("%d%d",&M,&H);
		int r=0;
		for(;H--;){
			scanf("%d%d",&a,&b);
			r=(r+mod_pow(a,b))%M;
		}
		printf("%d\n",r);
	}
	return 0;
}