本文共 1783 字，大约阅读时间需要 5 分钟。

题目描述

求 $a^b$ $mod$ $p$ 的值。

输入格式

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

输出格式

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

数据范围

$0$ $\le$ $a$ , $b$ $\le$ $10^9$

输入样例

3 2 7

输出样例

2

题解

算法1：直接计算 $O(b)$

直接使用C++中的 $pow(a,b)$ 函数计算$a$的$b$次方（当然也可以通过for循环实现此函数），再将最后的结果$mod$ $p$

code

#include
   
    using namespace std;long long a,b,p;//unsigned long long power(long long a,long long b)  //手写pow函数 //{   // long long result=1;//    for(int i=1;i<=b;i++)//        result=result*a;//    return result;//}int main(){       cin>>a>>b>>p;    unsigned long long x;    x=pow(a,b);//  x=power(a,b);    cout<
   

算法2：取模运算优化 $O(b)$

在算法1的基础上进行优化

code

#include
   
    using namespace std;long long a,b,p;long long power(long long a,long long b){    long long result=1;    for(int i=1;i<=b;i++)    {        result=result*a;     result%=p;  }     return result%p;}int main(){       cin>>a>>b>>p;    cout<
   

算法3：快速幂(正解) O(logb)

通过取模运算解决上了空间的问题，能够计算出正确的结果

code

#include
   
    using namespace std;long long a,b,p;long long power(long long a,long long b) {       long long result=1;    while(b>0)  {           if(b&1) result=result*a%p; //b&1等价于b%2==1         b>>=1; //power>>=1等价于power=power/2        a=(a*a)%p;    }    return result%p;}int main(){       cin>>a>>b>>p;    cout<