『算法-ACM 竞赛-数学-数论』欧拉降幂和广义欧拉降幂（实用好理解）

一般大佬会给你证明，而菜鸟会教你怎么使用。

先摆上公式：

$a^{b} \equiv \begin{cases}
a^{bmod\phi (p)} & \text gcd(a,p)=1 \
a^b & \text gcd(a,p)\neq 1,b<\phi (p)\
a^{bmod\phi (p)+\phi (p)} & \text gcd(a,p)\neq 1,b\geq \phi (p)
\end{cases} \ \ \ \ (modp)$

欧拉降幂：

$a^{b} \equiv a^{bmod\phi (p)} \ \ gcd(a,p)=1$
适用范围：
当底与取模的数互质，且 b 较大的时侯，我这句话用不到，直接扩展欧拉降幂就好了，时间复杂度差不了多少。

扩展欧拉定理：

$a^{b} \equiv \begin{cases}
a^b & \text gcd(a,p)\neq 1,b<\phi (p)\
a^{bmod\phi (p)+\phi (p)} & \text gcd(a,p)\neq 1,b\geq \phi (p)
\end{cases} \ \ \ \ \ (modp)$

总结：

用的时候我们只考虑扩展的就可以了，因为$bmod\phi (p)≡bmod\phi (p)+\phi (p)$

代码：

这个代码的优点是，如果 b 太大，不能读入的话也是可以处理的。
如果代码需要多次计算的话，可以使用线性筛法，获得欧拉函数的值。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;

inline ll read(ll m){
    register ll x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        x=x*10+ch-'0';
        if(x>=m) f=1;
        x%=m;ch=getchar();
    }
    return x+(f==1?m:0);
}

ll phi(ll n){
    ll ans=n,m=sqrt(n);
    for(ll i=2;i<=m;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 fast_pow(ll a,ll b,ll p){
    ll ret=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) ret=ret*a%p;
    return ret;
}

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

题目：
洛谷模板题