题目描述

快速求解 $ a^{n} \bmod b $
时间复杂度 $O( log(n) )$
注：这种题目，直接算 $ a^{n} \bmod b $肯定连long long都爆了。为了防止爆long long，只能拆解为若干项，迭代着求解，边迭代边求余数。

视频

【快速幂】 https://www.bilibili.com/video/BV1L867YmEEF/?share_source=copy_web&vd_source=6a3494b432f4f0cd85b8778d3e41c95f

暴力求法

时间复杂度 $O(n)$
$ a^{n} \bmod b = (a*a*a*a…) \bmod b$
不断迭代上市式括号中的内容,总共 $n$ 项，时间复杂度为 $O(n)$ 。
关键代码

LL res = 1;
for(int i = 0; i < n; i++){
    res=res * a % b;
}

快速幂法

预备知识——二进制分解

任意一个数字，都可即表示为若干个2的指数之和。
例如
$ 10=2^{3} +2^{1}$
$ 11=2^{3} +2^{1} +2^{0}$
$ 13=2^{3} +2^{2} +2^{0}$
原因：任何数都有对应的二进制数如13的二进制为‘1101’，1101=1000+100+1。而且不难看出，拆解出的2的最高次一定小于 $\log_{2}{13} $

算法思路

将n分解为若干个2的指数之和 $n=2^{m1} +2^{m2} +2^{m3}+…$
$ a^{n} \bmod b = a^{(2^{m1} +2^{m2} +2^{m3}+…)} \bmod b =(a^{2^{m1}} * a^{2^{m2}} * a^{2^{m3}} *… ) \bmod b $
只需迭代的将上式括号中的项即可，由于最多有$\log_{2}{n} $数量级的项，因此时间复杂度为$O( log(n) )$
例如求 $ 7^{13} \bmod 5 $
$ 7^{13} \bmod b = (7^{2^{3}} * 7^{2^{2}} * 7^{2^{0}} ) \bmod 5 $

LL res = 1;
int ni = n;//创建一个用于迭代的ni，含义为n的二进制去掉后i位
LL ai = a;//创建一个用于迭代的ai，含义为a^(2^i)%b
for(int i = 0; i <= log(n); i++){
    if(ni & 1) res = res * ai % b; //判断二进制最后一位是否为1；原理将ni的最后一位和1做“与”
    ni >>= 1; //去除二进制最后一位，将1010变为101
    ai = ai * ai %b;//a^(2^i+1)%b = {a^(2^i)%b * a^(2^i)%b} % b
}

样例

#include <iostream>
typedef long long LL;

using namespace std;

int main(){
    int N;//循环次数
    int a,n,b;//底数，幂，被除数
    cin>>N;
    while(N--){
        cin>>a>>n>>b;
        LL res = 1;
        int ni = n;//创建一个用于迭代的ni，含义为n的二进制去掉后i位
        LL ai = a;//创建一个用于迭代的ai，含义为a^(2^i)
        while(ni){
            if(ni & 1) res = res * ai % b; //判断二进制最后一位是否为1；原理将ni的最后一位和1做“与”
            ni >>= 1; //去除二进制最后一位，将1010变为101
            ai = ai * ai % b;
        }
        cout<< res<<'\n';
    }
}