51NOD 1046 A^B Mod C

给出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示例

用到了快速幂，挑战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 ;

}

递归版

巴特西

51NOD 1046 A^B Mod C

最新文章

热门文章