輸入a,n,k（1<=a,n<=1e9 1<=k<=10000 ，注意：有多組測(cè)試數(shù)據(jù)，請(qǐng)用EOF標(biāo)志判斷結(jié)束輸入）：
2 32 5
2 30 5
輸出(a^n)%k的結(jié)果（a的n次方被k除的余數(shù)）：
輸入a,n,k（1<=a,n<=1e9 1<=k<=10000 ，注意：有多組測(cè)試數(shù)據(jù)，請(qǐng)用EOF標(biāo)志判斷結(jié)束輸入）：
2 32 5
2 30 5
輸出(a^n)%k的結(jié)果（a的n次方被k除的余數(shù)）：
要求復(fù)雜度為O（logn）
解決思路,吃屎兄的推導(dǎo)的
(a*b)Mod c=((a Mod c)*b)Mod c
a^b Mod c 把B寫成二進(jìn)制(At ,At-1,At-2...A1,A0)
a^b Mod c =(a^(At*2^t....A0*2^0)mod c)=
((a^A0*2^0 mod c)*a^A1*2^1mod c).....
t=log2B;
下面是小弟的程序
#include <iostream>
using namespace std;
int convertToBin(int n,int (&arr)[14])
{
int i=0;
while(n)
{
arr[i]=n%2;
n=n/2;
i++;
}
return i;
}
int findAnswer(int k,int a,int arr[14],int bsize)
{
int ret = 1;
for(int i=0;i<bsize;i++)
{
if(arr[i])
ret=(ret*a*(1<<i))%k;
else
ret=(ret*(1<<i))%k;
}
return ret;
}
int main()
{
int a,n,k=1;
while(!cin.eof())
{
cin>>a;
if(a==-1) break;
cin>>n>>k;
int arr[14]={0};
int bsize = convertToBin(n,arr);
cout<<findAnswer(k,a,arr,bsize)<<endl;
}
}