#快速幂 #快速乘

题意

• 给定a,b,p,输出
• 其中a,b,p均为1e18量级

思路

• 纯粹的快速幂是不够的，因为中间的乘法就会爆炸
• 完全使用龟速乘全部转化为加法显然TLE
• 使用快速乘
  • 和快速幂类似，乘法变成加法，边加边模

ll mul(ll a,ll b,ll p){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}

代码

#include<bits/stdc++.h>

using namespace std;

using ll=unsigned long long;


ll mul(ll a,ll b,ll p){
    ll ans=0;
    while(b){
        if(b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}

ll qpow(ll a,ll b,ll p){
    ll ans=1;
    a%=p;
    while(b){
        if(b&1) ans=mul(ans,a,p);
        a=mul(a,a,p);
        b>>=1;
    }
    return ans;
}


int main(){
    int t;
    cin >> t;
    while(t--){
        ll a,b,p;
        cin >> a >> b >> p;
        cout << qpow(a,b,p) << endl;
    }
    return 0;
}


// __int 128乱搞
// ll qpow(ll a,ll b,ll p){
//     __int128 aa=a,bb=b;
//     aa%=p;
//     __int128 ans=1;
//     while(bb){
//         if(bb&1){
//             ans=ans*aa%p;
//         }
//         aa=aa*aa%p;
//         bb>>=1;
//     }
//     return (ll)ans;
// }

// int main(){
//     int t;
//     cin >> t;
//     while(t--){
//         ll a,b,p;
//         cin >> a >> b >> p;
//         cout << qpow(a,b,p) << endl;
//     }

//     return 0;
// }