Problem 1752 A^B mod C
Accept: 750 Submit: 3205
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63).
Input
There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.
Output
For each testcase, output an integer, denotes the result of A^B mod C.
Sample Input
3 2 4
2 10 1000
2 10 1000
Sample Output
1
24
24
二分快速幂模板题
#include <iostream>
#include <cstdio>
using namespace std;
#define ll __int64 ll quickadd(ll a,ll b,ll c) //运用快速幂的思想快速加,这样就不会溢出
{
ll ret=;
while(b)
{
if(b&)
{
ret+=a;
if(ret>=c) ret-=c; //这样比直接取模(ret%=c)更快
}
a<<=;
if(a>=c) a-=c;
b>>=;
}
return ret;
}
ll quickpow(ll a,ll b,ll c)
{
ll ret=;
while(b)
{
if(b&) ret=quickadd(a,ret,c);
a=quickadd(a,a,c);
b>>=;
}
return ret;
}
int main()
{
ll a,b,c;
while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
{
printf("%I64d\n",quickpow(a%c,b,c));
}
return ;
}