题目描述

求 a 的 b 次方对 p 取模的值。三个整数 a,b,p ,在同一行用空格隔开。

输入样例

3 2 7

输出样例

2

(快速幂) $O(logb)$

对于算法的理解还不够深刻，难免有所疏漏，还请大佬不吝赐教

时间复杂度分析：每次对b进行右移操作

感谢评论大佬分享
(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 = (yu1*yu2)%p;

本题逻辑核心！！
说明:以下a(n)为a^(2^n)
    1.对于(a^b)%p式子的展开
        a^b=1*a(x1)*a(x2)*a(x3).....
        a^b%p=( (1*a(x1)*a(x2)%p) * (a(x3)%p) ) %p
        1*a(x1)*a(x2)%p = ( (1*a(x1)%p) * (a(x2)%p) )%p
        1*a(x1)%p = ( (1%p) * (a(x1)%p) )%p
        所以res初始化值为1%p
        算法即是从下向上实现 
    2.理解a = a *a % p
        迭代a： ( res * (a(xn)%p) )%p 其中的a(xn)%p = a(xn-1)*a(xn-1)%p

C++ 代码

/*
    Name:AcWing 89. a^b
    Author:wyz
    Date:2019/3/31 8:29:59
    Note:

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
    ll a,b,p;//求a的b次方模p的结果
    cin>>a>>b>>p;
    a%=p;//这个可加可不加，加上有助于理解公式 
    ll res = 1 % p;//如果p为1的话，那么无论什么数的结果都是0;
    while(b){
        //res*a % p = ((res%p)*(a%p))%p
        //res是已经mod过p的，所以等式右侧的(res%p)是无需再操作的。 
        if(b&1)//如果二进制下的最后一位是1
            res= res * a % p; //操作为等式左边 
        a=a * a % p;//倍增a=a*a(幂次*2),实现等式右边(a%p)操作
        b>>=1;//b右移一位，遍历下一位； 
    }
    cout<<res<<endl;

    return 0;
}