欧拉降幂（扩展欧拉定理）

前言：之前+看过欧拉降幂，但误以为gcd(a,mod) > 1也能之间加上phi(mod), 在一次网络名额赛中有道裸欧拉降幂，接下来就是自己写着只有理论上的欧拉降幂来写题，硬搞了4个小时才A了。本想着不能在一个地方失败两次来写了这篇博客。

附上公式：

当 $b < p h i (m) $ 时， $a^{b} % m = a^{b} % m $
当 $b \geq p h i (m)$ 时， $a^{b} % m = a^{b % p h i (m) + p h i (m)} % m $

当 $g c d (a, m) = 1 $ 时候，根据欧拉定理 $a^{p h i (m)} % m = 1 $ , 很容易得出。

当 $g c d (a, m) > 1$ 时，根据剩余系得出循环节可以证明公式成立(我也不会)

参考：https://blog.sengxian.com/solutions/uva-10692

例题：UVA10692

求 $a_{1}^{a_{2}^{a_{3}^{. . .}}} % m$ 的值，

思路：

反复使用欧拉降幂即可，注意需要处理 $b < p h i (m)$ 的情况。

对于这种情况可以考虑快速幂的时候先试乘，如果不超直接返回结果，否则返回取余再加的结果，可以归纳证明该算法是正确的。不过要在最后返回的时候取余m。

不过这题数据比较水，随便写都能过，推荐看下面计蒜客那题

代码：

#include<bits/stdc++.h>
using  namespace  std;
typedef long long ll;  
const int maxn=1e6+10;  
ll a[maxn],phi[maxn];  
ll exmod(ll a,ll m)  
{  
    return a>=m?a%m+m:a;  
}  
ll exqpow(ll a,ll b,ll mod)//a^b>=m 返回a^b%m+m,否则返回a^b 
{  
    ll ans=1;  
    while(b)  
    {  
        if(b&1)  
            ans=exmod(ans*a,mod);  
        b>>=1;  
        a=exmod(a*a,mod);  
    }  
    return ans;  
}  
ll getphi(ll x)  
{  
    if(phi[x]!=-1) return phi[x];  
    ll xx=x,ans=x;  
    for(ll i=2; i*i<=x; i++)  
    {  
        if(x%i==0)  
        {  
            ans=ans*(i-1)/i;  
            while(x%i==0)  
                x/=i;  
        }  
    }  
    if(x>1)  
        ans=ans*(x-1)/x;  
    phi[xx]=ans;  
    return ans;  
}  
int n;//a[]的个数 
//val=a[k]^(a[k+1]^(a[k+2]^(...^a[n]))) 
//现在准备计算val%m,且val>=m返回val%m+m,否则返回val 
ll solve(int k,ll m)  
{  
    //并且注意m==1时,a>0应该返回m.这里在exmod会自动计算 
    if(k==n||m==1) return exmod(a[k],m);//大优化，从满数据迭代到1不会太多次 
    return exqpow(a[k],solve(k+1,getphi(m)),m);  
}  
char s[110];  
int main()  
{  
    memset(phi,-1,sizeof(phi));  
    int cas=0;  
    while(scanf("%s",s)&&s[0]!='#')  
    {  
        //m为模数,n个数,求a1^(a2^(a3^(...)))%m 
        ll m;  
        sscanf(s,"%lld",&m);  
        cin>>n;  
        for(int i=1;i<=n;++i)  
            cin>>a[i];  
        cout<<"Case #"<<++cas<<": "<<solve(1,m)%m<<endl;  
    }  
    return 0;  
}

题目：计蒜客-super_log

题意：

给出a,b,m。计算 $a^{a^{a^{. . .}}} % m$ ,这里的a有b个

这题的数据是非常强的。

#include<bits/stdc++.h>
using  namespace  std;
typedef long long ll;
const int maxn=1e6+10;
const int maxm=1e6+10;
ll phi[maxm];
ll exmod(ll a,ll m)
{
    return a>=m?a%m+m:a;
}
ll exqpow(ll a,ll b,ll mod)//a^b>=m 返回a^b%m+m,否则返回a^b
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=exmod(ans*a,mod);
        b>>=1;
        a=exmod(a*a,mod);
    }
    return ans;
}
ll getphi(ll x)
{
    if(phi[x]!=-1) return phi[x];
    ll xx=x,ans=x;
    for(ll i=2; i*i<=x; i++)
    {
        if(x%i==0)
        {
            ans=ans*(i-1)/i;
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        ans=ans*(x-1)/x;
    phi[xx]=ans;
    return ans;
}
int n;
ll a;
ll solve(int k,ll m)
{
     //并且注意m==1时,应该返回m.因为a>0这里在exmod会自动计算
    if(k==n||m==1) return exmod(a,m);//大优化，从满数据迭代到1不会太多次
    return exqpow(a,solve(k+1,getphi(m)),m);
}
int main()
{
    memset(phi,-1,sizeof(phi));
    int t;
    cin>>t;
    while(t--)
    {
        ll m;
        cin>>a>>n>>m;
        if(n==0){
            cout<<1%m<<endl;
        }
        else
            cout<<solve(1,m)%m<<endl;
    }
    return 0;
}