习题：Huge Mods（欧拉定理）

题目

传送门

思路

挺好的一道拓展欧拉定理的板子题

我们已知\(a^b\%m=a^{b\%\varphi(m)+\varphi(m)}\%m\)

当然此时\(b>=\varphi(m)\)

也就是说，我们可以从上至下的一层一层的算，

但是每一层的模数是不一样的

具体来说第i层的模数是\(\varphi\varphi... m\),i-1个\(\varphi\)

\(a^{b^c}\%m=a^{b^{c\%\varphi(\varphi(m))+\varphi(\varphi(m))}\%\varphi(m)+\varphi(m)}\%m\)

代码

#include<iostream>
#include<cstdio>
using namespace std;
int tot;
long long mod;
long long n;
long long a[15];
long long ex_oular(long long x,long long mod)
{
    if(x>=mod)
        return x=x%mod+mod;
    else
        return x;
}
long long qkpow(long long a,long long b,long long mod)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    long long t=qkpow(a,b/2,mod);
    t=ex_oular(t*t,mod);
    if(b%2==1)
        t=ex_oular(t*a,mod);
    return t;
}
long long varphi(long long n)
{
    long long ans=n;
    for(int i=2;1ll*i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(!(n%i))
            {
                n/=i;
            }
        }
    }
    if(n>1)
    {
        ans-=ans/n;
    }
    return ans;
}
long long solve(long long x,long long k)
{
    //cout<<k<<' '<<n<<'\n';
    //getchar();
    if(k==n)
    {
        return ex_oular(a[k],x);
    }
    long long phi=varphi(x);
    return qkpow(a[k],solve(phi,k+1)+phi,x);
}
int main()
{
    //ios::sync_with_stdio(false);
    while(cin>>mod)
    {
        if(mod=='#')
            break;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        cout<<"Case #"<<++tot<<": "<<solve(mod,1)%mod<<'\n';
    }
    return 0;
}