题解 | #华华教月月做数学#

下面是关于由分治思想衍生的快速幂和快速乘算法的题解 首先，我们提出问题：为什么要用快速幂算法，因为数据太大有可能导致爆数据范围，而且更加重要的一点是当数据越来越大时n与logn的差异越来越显著，然后快速幂算法中的乘法也有爆数据范围的风险，所以我们这里借鉴一下快速幂算法思想，举一反三出快速乘算法，也就是比如说A等于6，B等于5（101），那么我们把5分成11 + 02 + 1*4,然后每次从最底层的二进制数开始，把6这其中一个乘数作为基本数据单位，分别加入到答案ans中，再在中间穿插%操作，防止爆数据范围。 妙，太妙了！

using namespace std;
long long kuaisucheng(long long a , long long b , long long p){
    long long ans = 0;//这里就是快速乘算法的实现步骤
    while(b != 0){
        if(b & 1 == 1 ){
        ans = (ans + a )% p;//但说实话本人在此处有一个疑点，这样的加法难道不会爆吗？
        }
        a = a * 2 % p;//这里就是快速幂算法思想的快速借鉴
        b >>= 1;
    }
    return ans;
}
long long kuaisumi(long long a,long long b,long long p){
    long long ans = 1 ;//这里是快速幂算法
    while(b != 0){
        if (b & 1 == 1){
            ans = kuaisucheng(ans,a,p) % p;//因为快速乘函数中最后的答案没有对其进行取模的操作，所以我们这里需要对此进行最后的取模操作，下面的基本数据单位也是如此
        }
        a = kuaisucheng(a,a,p);a %= p;
        b >>= 1;
    }
    return ans % p;
}
int main(){
    int t;
    cin >> t;
    long long a,b,p;
    for (int i = 1; i <= t; i ++ ){
        cin >> a >> b >> p; 
        cout << kuaisumi(a, b, p) << endl；
    }
    return 0;
}

链接