浙江工业大学1052
整数次幂取模
Time Limit:1000MS Memory Limit:32768K
Description:
给定一个数，其值用A的B次方表示(B<100000)，求该数除以一个整数C（<100000）所得的余数。注意算法的合理性，其性能有一定的要求。每行有三个数，依次表示A，B，C，每行对输出对应的余数。
Sample Input:
1 2 3
2 1 3
3 3 5
Sample Output:
1
2
2
源代码：
#include<iostream>
using namespace std;
long power(long A,long B,long C)
{
if(B==0){
return 1;
}
if(B==1){
return A%C;
}
long tmp = power(A,B/2,C);
if(B&1==1){
return (((tmp*tmp)%C)*(A%C))%C;
}else{
return (tmp*tmp)%C;
}
return 0;
}
int main()
{
long A,B,C;
while(scanf("%ld%ld%ld",&A,&B,&C)!=EOF){
printf("%ld\n",power(A,B,C));
}
return 0;
}
/**//*long long PowerMod(long long a, int b, int k)
{ //(a^b )%k
long long tmp = a, ret = 1;
for(; b ; b>>1 )
{
if (b & 1)
ret = (ret * tmp) % k; //只是每步运算的时候都取模
tmp = (tmp * tmp) % k;
}
return ret;
}*/