题目描述

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

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

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

数据范围
0≤a,b≤109

1≤p≤109

样例

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

模板算法快速幂，本题可采用二进制的方式运算
如果利用暴力算类似于325443的2432212242312，超过1e9,必然会超时
本题输入a,b,p
可利用二进制性质，将b转换为二进制数
例如a = 2, b = 9
2 ^ 9 = 512
本题可以这样算9的二进制是1001 枚举这四个数
枚举到1时res*a 每枚举一次运行一次 a = a * a
这样即可

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL f(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = (LL)res * a % p;
        b >>= 1;
        a = (LL)a * a % p;
    }
    return res % p;//防止b==0，不运行就直接传回值了
}

int main()
{
    LL a, b, p;
    cin >> a >> b >> p;
    cout << f(a, b, p);
}