题目描述

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

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

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

数据范围
0≤a,b,p≤10^9
数据保证 p≠0

样例

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

二进制转换

通过“右移(>>)”“与(&)”运算的结合，遍历了b的二进制表示的下一位，累积到ans中

时间复杂度

$O(log(2,b))$

参考文献

蓝书

C++ 代码

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
int power(int a,int b,int p)
{
    int ans=1%p;
    for(;b;b>>=1)
    {
        if(b&1)ans=(long long)ans*a%p;
        a=(long long)a*a%p;
    }
    return ans;
}
int main()
{
    int a,b,p;
    cin>>a>>b>>p;
    int ans=power(a,b,p);
    cout<<ans<<endl;
    return 0;

}