C++|龟速乘&&快速幂

应用场景

当 p > sqrt(整型最大值) 时，两个已在 [0, p-1] 范围内的数相乘就可能溢出，这时就必须用慢速乘（龟速乘）替代直接乘法。
p ≤ 1e9：直接 (a % p) * (b % p) % p 基本安全（实际安全线是 3e9）。
p > 2e9 ~ 3e9 以上：就必须用慢速乘，否则乘积溢出会导致错误结果。

龟速乘 

#include<bits/stdc++.h> 
using namespace std;
#define int long long 
int SlowMultiplication(int a,int b,int p){
    int ans=0;
    a%=p;
    while(b){
        if(b&1)ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}
signed main(){
    int a, b, p;
    cin>>a>>b>>p;
    cout<<SlowMultiplication(a,b,p)<<'\n';
   return 0;
}

快速幂 

#include<bits/stdc++.h> 
using namespace std;
#define int long long 
int ExponentiationBySquaring(int a, int b, int p){
    a%=p;
    int ans=1;
    while(b){
        if(b&1)ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
signed main(){
    int a,b,p,ans;
    cin>>a>>b>>p;
    cout<<ExponentiationBySquaring(a,b,p)<<'\n';
   return 0; 
}

龟速乘&&快速幂 

#include <bits/stdc++.h> 
using namespace std;
#define int long long 
int SlowMultiplication(int a,int b,int p){
    int ans=0;
    a%=p;
    while(b){
        if(b&1)ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}
int ExponentiationBySquaring(int a, int b, int p){
    a%=p;
    int ans=1;
    while(b){
        if(b&1)ans=SlowMultiplication(ans,a,p);
        a=SlowMultiplication(a,a,p);
        b>>=1;
    }
    return ans;
}
signed main(){
    int a,b,p;
    cin>>a>>b>>p;
    cout<<ExponentiationBySquaring(a,b,p)<<'\n';
    return 0;
}