取模意义的快速幂黑科技：龟速乘

一般的快速幂：

ll ksm(ll a,ll n,ll m){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*a%m;
        a=a*a%m;
        n>>=1;
    }
    return ans;
}

这样会存在一个问题，当求$a^b\pmod{m}，$且$a>10^9$时，会存在爆$long\ long$的问题，这时候我们需要对乘法取模进行改正，于是便有了龟速乘。

---

龟速乘：

为什么要叫龟速乘呢，因为这个乘法运算比计算机底层的乘法速度要慢。
先看代码：

ll qmul(ll x,ll y,ll m){    //龟速乘 
    ll s=0;
    while(y){
        if(y&1) s=(s+x)%m;
        x=(x+x)%m;
        y>>=1; 
    }
    return s;
}

形式与快速幂非常相似，只不过里面的乘法变成加法了，
比如$2\times 5= 2+2\times 4=2+4\times 2=2+8=10$。

时间复杂度：$O(logy)$

快速幂和龟速乘搭配一起就可以欢乐地进行模意义下的快速幂了。

复杂度：$O(logn\times log(a))$

ll qmul(ll x,ll y,ll m){    //龟速乘 
    ll s=0;
    while(y){
        if(y&1) s=(s+x)%m;
        x=(x+x)%m;
        y>>=1; 
    }
    return s;
}
///////////////
ll ksm(ll a,ll n,ll m){
    ll ans=1;
    while(n){
        if(n&1) ans=qmul(ans,a,m);
        a=qmul(a,a,m);
        n>>=1;
    }
    return ans;
}

---

例题： U55950 【模板】扩展欧拉定理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
bool f;
inline void read(ll &s){
    int w=1;char c;
    while(c=getchar(),!isdigit(c)){
        if(c=='-') w=-1;
    }
    while(isdigit(c)) s=(s<<3)+(s<<1)+(c&15),c=getchar();
    s*=w;
}
inline ll readm(ll m){
    ll s=0;char c;while(c=getchar(),!isdigit(c)) ;
    while(isdigit(c)){
        s=(s<<3)+(s<<1)+(c&15);
        if(s>=m){
            s%=m;
            f=true;        
        }
        c=getchar();
    }
    return s;
}
ll phi(ll n){
    ll s=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            s-=s/i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) s-=s/n;return s;
}
ll qmul(ll x,ll y,ll m){    //龟速乘 
    ll s=0;
    while(y){
        if(y&1) s=(s+x)%m;
        x=(x+x)%m;
        y>>=1; 
    }
    return s;
}
ll a,m,b;
ll ksm(ll a,ll n,ll m){
    ll ans=1;
    while(n){
        if(n&1) ans=qmul(ans,a,m);
        a=qmul(a,a,m);
        n>>=1;
    }
    return ans;
}
int main(){
    read(a),read(m);ll phim=phi(m);b=readm(phim);
    printf("%lld\n",ksm(a,b+(f?phim:0),m));
    return 0;
}