题目描述

求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数，表示a^b mod p的值。

数据范围
0≤a,b,p≤109

样例

输入样例：
3 2 7
输出样例：
2

题解

数学证明：

 (a * b ) % p = ((a % p ) * ( b % p) ) % p ; ( a +b ) % p = (( a % p ) + (b % p) ) % p ;
   证明仅以a * b % p；
       a = c1 * p + yu1 ; b = c2 * p + yu2;
        ((a* b)) % p = ((c1 * p + yu1 ) * (c2 * p+ yu2 )) % p = 展开就ok了

      a = (long long)a * a % p; 这里是倍增，每次求 a^2^1%p,a^2^2%p,a^2^3%p,…a^2^1%p,a^2^2%p,a^2^3%p,… 的值;
     if (b & 1) res = (long long)res * a % p; 这里是求指数 b 的二进制表示，如果第 k 位是1，就乘上对应的 a^2^k;

时间复杂度分析：blablabla

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int a, b, p;
    cin >> a >> b >> p;

    int res = 1 % p;
    while (b)
    {
        if (b & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }

    cout << res << endl;

    return 0;
}