【模板】扩展欧拉定理

题目大意：求\[a^b\ mod \ m\]

题解：

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a,m,phi;

ll read(){
    ll x=0,f=0;char ch;
    do{ch=getchar();}while(!isdigit(ch));
    do{
        x=x*10+ch-'0';ch=getchar();
        if(x>=phi)f=1;
        x%=phi;
    }while(isdigit(ch));
    return f?x+phi:x;
}
ll calc(ll n){
    int ans=n;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
ll fpow(ll n,ll b,ll c){
    ll res=1%c;
    for(;b;b>>=1,n=n*n%c)if(b&1)res=res*n%c;
    return res;
}


int main(){
    scanf("%d%d",&a,&m);
    phi=calc(m);
    ll b=read();
    printf("%lld\n",fpow(a,b,m));
    return 0;
}

【模板】扩展欧拉定理

原文：https://www.cnblogs.com/wzj-xhjbk/p/10576295.html