PKU演習問メモ(2010/3/27)

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