题目描述

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

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

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

数据范围
$0≤a,b,p≤109$
数据保证 $p≠0$
输入样例：

3 2 7

输出样例：

2

样例

blablabla

算法1

(快速幂) $O(log(k))$

这里个人习惯用k代替b！

利用快速幂求解。
注意特判！！！

时间复杂度

$O(log(k))$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int qmi(int a, int k, int p)
{
    int res = 1;
    if(p == 1) return 0;
    if(k == 0) return 1;
    if(a == 0) return 0;
    while(k)
    {
        if(k & 1) res = (long long)res * a % p;
        k >>= 1;
        a = (long long ) a * a % p;
    }
    return res;
}
int main()
{
    int a, k, p;
    scanf("%d%d%d", &a, &k, &p);
    printf("%d", qmi(a, k, p));
}

这些特判其实也可以省略掉，但是有些题时间复杂度会变高。