HDu 1420(Prepared for New Acmer)(中国の残りの定理)(べき乗を下げる法)

Prepared for New Acmer
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6516    Accepted Submission(s): 2450
Problem Description
合宿は2週間近く行われたが、この間は回復的な訓練を主とし、私はずっとみんなの訓練状況に注目していた.ここでは特に今回のDP特別テーマ練習試合にテーマとテストデータを提供してくれた合宿チームのキャプテンxhdさんに感謝します.
特に嬉しいことに、合宿チームの訓練に尾行した新しい選手たちはよく演技し、進歩も著しい.特に訓練態度は私の予想を大きく上回っている.
新しい選手がまだシステム訓練を受けていないことを考慮して、私はここで特に簡単な問題に参加しました.
3つの正の整数A,BとC(A,B,C<=100000)を与え、A^B mod Cの結果を求める.
みんながすべて试合の中でACの楽しみを体得することができることを望んで、绝対的なカスタマイズ、とても高い待遇、ほほほ...
 
Input
入力データは、最初に正の整数Nを含み、試験例の個数を表し、次にN行のデータであり、各行は3つの正の整数A,B,Cを含む.
 
Output
各テストインスタンスについて計算結果を出力し、各インスタンスの出力が1行を占めます.
 
Sample Input

   
     

      
    3
2 3 4
3 3 5
4 4 6
   
     

 
Sample Output

   
     

      
    0
2
4
   
     

 
Author
lcy
 
Source
ACM夏休み合宿チーム練習試合(二) 
テーマ分析:
この問題を解くには、まずこの式を知っておく必要があります.(a*a)%c=((a%c)*(a%c)))%%c......式1.
次に降順法で、例を挙げて詳しく話しましょう.
3^8=3^4*3^4=(3^2*3^2)*(3^2*3^2)=((3*3)*(3*3)*(3*3)*(3*3)*(3*3)*(3*3))、3^8%5が要求されたと仮定し、まず3%5を求め、
式1に基づいて3^2%5,3^4%5,3^8%5を順次求めることができ,これは2を除いてべき乗を下げる過程である.
1回に2を除いた降順が奇数になる可能性があることに注意してください.この場合、まず1つを取り出してから降順します.
例えば3^10=3^5*3^5(べき乗5、奇数)=(3^2*3^2*3)*(3^2*3^2*3)=......
以下から抜粋:
クリックしてリンクを開く
心得:
大いに利益を得て,ものを学んだ.
コードは次のようになります.

#include<stdio.h> 
int main()
{
	int i,n,a,b,c;
	scanf("%d",&n);
	while(n--)
	{
		__int64 temp,sum;
		scanf("%d%d%d",&a,&b,&c);
		sum=a%c;
		temp=1;
		while(b>1)//       ，   a%c           
		{
			if(b&1)//    ，      
			{
				temp*=sum;//temp                
				temp%=c;
				b--;//     ，     
			}
			else
			{
				sum*=sum;//    
				sum%=c;
				b/=2;//        ，        
			}
		}
		printf("%I64d
",sum*temp%c);
	}
	return 0;
}