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; }