P1405 苦惱的小明（歐拉降幂）

題目連結：https://www.luogu.com.cn/problem/P1405

思路：

先要知道什麼是歐拉定理：如果a，m互質，則a^b %m = a^(b%phi(m) + phi(m) ) %m

然後将每一步都寫出來，eg：a^b^c^d

ans = a^(t1 %phi(m) + phi(m) ) %m , p1 = phi(m);

t1 = b^(t2 % phi(p1) + phi(p1) ) % p1 , p2 = phi(p1);

t2 = c^(t3 % phi(p2) + phi(p2) ) % p2 , p3 = phi(p2);

t3 = c^(t4 % phi(p3) + pihi(p3) ) % p3 , p4 = phi(p3);

t4 = d;

是以，可以遞歸去做，這題與bzoj 3884的解法一樣。

代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+10;
const ll mod = 10007;
ll a[N];
int n;
ll qpow(ll x,ll y,ll m)
{
    ll res = 1ll;
    while(y)
    {
        if(y&1) res = res*x%m;
        x = x*x%m;
        y >>= 1;
    }
    return res;
}
ll eular(ll x)
{
    ll res = x,tp = (ll)sqrt(1.0*x);
    for(ll i=2;i<=tp;i++)
    {
        if(x%i == 0)
        {
            res = res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res = res/x*(x-1);
    return res;
}
ll f(int id,ll m)
{
    if(id == n) return a[n];
    ll phi = eular(m);
    ll p = f(id+1,phi)%phi +phi;
    return qpow(a[id],p,m);
}
int main(void)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll res = f(1,mod);
    printf("%lld\n",res);
    return 0;
}