51nod1046 A^B Mod C题解

1046 A^B Mod C

给出3个正整数A B C，求A^B Mod C。

例如，3 5 8，3^5 Mod 8 = 3。

输入

3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)

输出

输出计算结果

输入样例

3 5 8

输出样例

3

本题运用快速幂的思路解决，直接暴力会超时，注意开long long

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 ll FastPower(ll a,ll b,ll c)
 6 {
 7     ll ans=1;
 8     while(b!=0)
 9     {
10         if(b&1)//当b为奇数时 
11         {
12             ans=ans*a%c;//直接模 c 即可 
13         }
14         a=(a*a)%c;//a自身乘，准备为ans做贡献 
15         b>>=1;//b除以2 
16     }
17     return ans;
18 }
19 int main()
20 {
21     ll a,b,c;
22     while(scanf("%lld%lld%lld",&a,&b,&c)!=EOF)
23     {
24     ll ans=FastPower(a,b,c);
25     cout<<ans%c<<endl;    
26     }
27     return 0;
28 }