【luoguP5091】【模板】欧拉定理

题目链接

欧拉定理：

当\(a\),\(m\)互质时，\(a^{\phi(m)}\equiv 1 (mod ~ m)\)

扩展欧拉定理：

当\(B>\phi(m)\)时，\(a^B\equiv a^{B~mod~\phi(m)+\phi(m)}\)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;

int a,m,b;
bool flag;

inline int read(int MOD){
    int x=0; char c=getchar();
    while(c<'0') c=getchar();
    while(c>='0'){
        x=x*10+c-'0';
        if(x>MOD) flag=1,x%=MOD;
        c=getchar();
    }
    return x;
}

inline int mul(int x,int y,int MOD){
    int s=0;
    while(y){
        if(y&1) s=(s+x)%MOD;
        y>>=1;
        x=(x+x)%MOD;
    }
    return s;
}

inline int qpow(int x,int k,int MOD){
    int s=1ll%MOD;
    while(k){
        if(k&1) s=mul(s,x,MOD);
        k>>=1;
        x=mul(x,x,MOD);
    }
    return s;
}

signed main()
{
    scanf("%lld%lld",&a,&m);
    int phi=m;
    int k=sqrt(m),x=m;
    for(int i=2;i<=k;++i)
        if(x%i==0){
            while(x%i==0) x/=i;
            phi=phi/i*(i-1);
        }
    if(x!=1) phi=phi/x*(x-1);
    b=read(phi);
    if(flag)
        printf("%lld\n",qpow(a,b+phi,m));
    else printf("%lld\n",qpow(a,b,m));
    return 0;
}

【luoguP5091】【模板】欧拉定理

原文：https://www.cnblogs.com/yjkhhh/p/11715767.html