P1405 苦恼的小明

· · 题解

非常好数论题，使我大脑旋转。

思路

给定一个序列 a_1 至 a_n，求 a_1^{a_2^{\cdots^{a_n}}}\bmod 10007 的值。 首先看到这么多次幂，尝试使用扩展欧拉定理使其降一下幂。

扩展欧拉定理：

& a^b,\ b<\varphi(m)\\ & a^{b\bmod \varphi(m)+\varphi(m)},\ b\ge\varphi(m) \end{cases}\pmod m$，其中 $\varphi(n)$ 表示欧拉函数，即小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。 那么式子就先被化成了 $a_1^{(a_2^{\cdots^{a_n}})\bmod\varphi(a_2^{\cdots^{a_n}})+\varphi(a_2^{\cdots^{a_n}})}\bmod 10007$， 再用一次扩展欧拉定理，化成了 $a_1^{(a_2^{(a_3^{\cdots^{a_n}}\bmod\varphi(a_3^{\cdots^{a_n}})+\varphi(a_3^{\cdots^{a_n}}))})\bmod\varphi(a_2^{\cdots^{a_n}})+\varphi(a_2^{\cdots^{a_n}})}\bmod 10007$，同理递推。 但是我们懒，不愿意递推怎么办？我们可以先预处理求一遍 $\varphi(1)$ 到 $\varphi(n)$ 的值，然后从 $a_n

开始进行快速幂，指数为上一次快速幂求出的值，底数为 a_i（如果 a_i\ge\varphi(i) 时，底数应为 a_i\bmod \varphi(i)+\varphi(i)），模数为 \varphi(i)第 i 次求 a_{i-1} 的指数，最后一次得出的值就是答案。

最后输出时别忘了取模。

Code

#include<bits/stdc++.h>
#define M 11451411
#define ll long long
using namespace std;
ll n,tmp,ans=1,phi[M],num[M];
const ll mod=10007;
ll qpow(ll x,ll y,ll m)
{
    ll res=1;
    while(y)
    {
        if(y&1)res=res*x%m+m;
        y>>=1;
        x=x*x%m+m;
    }
    return res;
}
int main()
{
    scanf("%lld",&n);
    phi[1]=mod;
    for(ll i=2;i<=n+114;i++)
    {
        tmp=phi[i-1];
        phi[i]=1;
        for(ll j=2;j*j<=tmp;j++)
        {
            if(tmp%j)continue;
            phi[i]*=j-1;
            tmp/=j;
            while(!(tmp%j))phi[i]*=j,tmp/=j;
        }
        if(tmp>1)phi[i]*=(tmp-1);
    }
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        if(phi[i]<num[i])num[i]=num[i]%phi[i]+phi[i];
    }
    for(ll i=n;i>=1;i--)ans=qpow(num[i],ans,phi[i]);
    printf("%lld",ans%mod);
    return 0;
}