题解：P1226 【模板】快速幂

MoCaRabbit · 2025-03-04 17:24:53 · 题解

求 a^b\bmod p。

算法介绍

快速幂算法可以以 O(\log b) 的时间复杂度求出。

根据初一数学，如果 b\bmod 2=1，有 a^b=(a^{\lfloor\frac{b}{2}\rfloor})^2\times a，否则有 a^b=(a^{\frac{b}{2}})^2。

于是两种情况都可以递归到子任务 (a^{\lfloor\frac{b}{2}\rfloor})^2。

最后递归到 a^0=1 直接返回吧。

可以很好的写出代码。

inline int power(int x,int y,int p){//这是快速幂函数
    if(y==0) return 1;
    int tot=power(x,y>>1,p);
    if(y&1) return tot*tot%p*x%p;//注意取模
    else return tot*tot%p;
}

正确性证明

发现每次 b 的大小都减半，所以时间复杂度是 O(\log b) 的。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,p;
inline int power(int x,int y,int p){
    if(y==0) return 1;
    int tot=power(x,y>>1,p);
    if(y&1) return tot*tot%p*x%p;
    else return tot*tot%p;
}
signed main() {
    cin>>a>>b>>p;
    cout<<a<<"^"<<b<<" mod "<<p<<"="<<power(a,b,p);
    return 0;
}