- 1617 Crypto Columns
- 平文の順序を変えた暗号文を復号する問題。そのまま実装すればいい。
- 1799 Yeehaa!
- 半径Rの大きい円のにn個の半径rの小さい円が輪になって内接している。Rとnが与えられたときの小さい円の半径rを求める問題。方程式を立てて解く。昔なんで間違ったんだろ???
- 1995 Raising Modulo Numbers
- Mと数列a[i],b[i]が与えられたとき、Σai^bi mod Mを求める問題。繰り返し二乗法を使えばいい。フェルマーの小定理を使えば計算量が若干小さくなる(繰り返し二乗法で通るので要らないけど)
1995 Raising Modulo Numbers
int modpw(int a,int b,int m)
{
if(a==0||m==1)return 0;
int pw[32],bit[32]={0},d=0,ret=1;
pw[0]=a;
for(int t=b;t;t>>=1)bit[d++]=t&1;
rep(i,d-1)pw[i+1]=(pw[i]*pw[i])%m;
rep(i,d)if(bit[i])ret=(ret*pw[i])%m;
return ret;
}
int main()
{
int CS; scanf("%d",&CS);
rep(cs,CS)
{
int m,n;
scanf("%d%d",&m,&n);
int ans=0;
rep(i,n)
{
int a,b;
scanf("%d%d",&a,&b);
ans+=modpw(a%m,b,m);
}
cout<<ans%m<<endl;
}
return 0;
}