WOJ-701：阶乘幂（拓展欧拉定理降幂）

利用拓展欧拉定理降幂。

我们发现对一个数取欧拉函数，log次就会变成1，而任何数模1肯定=0，所以就可以算出来了。

然而有的后面的phi[m]这一项需要加，有的不需要加。

因为这个不断地幂次增长速度极快，很少几项就能够增长到远大于模数的地步。

所以我们可以先暴力处理前几项判断即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll POW(ll x,ll n,ll MOD)
{
    ll res=1;
    x%=MOD;
    while(n)
    {
        if(n%2)res=res*x%MOD;
        x=x*x%MOD;
        n/=2;
    }
    return res;
}
ll f(int x)        //求x的欧拉函数值
{
    ll ans=x;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            ans/=i;
            ans*=i-1;
            while(x%i==0)x/=i;
        }
    }
    if(x>1)
    {
        ans/=x;
        ans*=x-1;
    }
    return ans;
}
ll cal(ll n,ll m)
{
    if(n%m==0)return 0;
    if(n==1)return 1;
    ll last=max(n-5,1ll),pre,phi=f(m);
    for(int i=max(n-5,1ll)+1;i<n;i++)
    {
        ll pre=last;
        last=1;
        while(pre--)
        {
            last*=i;
            if(last>=phi)return POW(n,cal(n-1,phi)+phi,m);
        }
    }
    return POW(n,last,m);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)printf("%lld\n",cal(n,m)%m);
    return 0;
}