
给出3个正整数A B C,求A^B Mod C。
例如,3 5 8,3^5 Mod 8 = 3。
Input
3个正整数A B C,中间用空格分隔。(1 <= A,B,C <= 10^9)
Output
输出计算结果
Input示例
3 5 8
Output示例
3
用到了快速幂 ,挑战P123
比如x ^22 = x ^16 *x ^4*x ^2;
22 转换成二进制是10110;
#include <iostream>
using namespace std;
typedef long long ll; ll pow_mod(ll x,ll n,ll mod)
{
ll res = ;
while ( n > )
{
if(n & ) res = res * x % mod;
x = x * x % mod;
n >>= ;
//cout<< n << endl;
}
return res;
} int main()
{
int x,n,mod;
cin >> x >> n >> mod;
cout<<pow_mod(x,n,mod)<<endl;
return ;
}
利用位进制
下面是递归版本
如果n为 偶数 那么 x^n = (x^2) ^ (n/2) n为奇数 无非多乘一个n
#include <iostream>
using namespace std;
typedef long long ll; ll pow_mod1(ll x,ll n,ll mod)
{
ll res = ;
if(n == ) return ;
res = pow_mod1(x * x % mod, n/,mod);
if(n % )
res = res * x % mod;
return res;
} int main()
{
int x,n,mod;
cin >> x >> n >> mod;
cout<<pow_mod1(x,n,mod)<<endl;
return ;
}
递归版