NCPC2016-E- Exponial

Illustration of exponial(3) (not to scale),Picture by?C.M. de Talleyrand-Périgord via Wikimedia Commons?Everybody loves big numbers (if you do not,you might want to?stop reading at this point). There are many ways of constructing?really big numbers known to humankind,for instance:
In this problem we look at their lesser-known love-child the?exponial,which is an operation de?ned for all positive integers?n as
For example,exponial(1) = 1 and??

which is already?pretty big. Note that exponentiation is right-associative:??

.
Since the exponials are really big,they can be a bit unwieldy to work with. Therefore?we would like you to write a program which computes exponial(n) mod m (the remainder of?exponial(n) when dividing by m).

The input consists of two integers n (1 ≤ n ≤ 109?) and m (1 ≤ m ≤ 109?).

Output a single integer,the value of exponial(n) mod m.

2 42

2

a^b %c= a^(b%phi(c)+phi(c)) %c (b>=phi(c)） 
如果 phi(c)>b 直接 a^b%c

对这个题来说，当n>4可以直接用这个算了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll fi(ll n)
{
    ll ans=n;
    for (int i=2;i*i<=n;i++)
    {
        if (n%i==0)
        {
            ans-=ans/i;
            while (n%i==0) n/=i;
        }
    }
    if (n>1) ans-=ans/n;
    return ans;
}
 
ll qpow(ll a,ll n,ll m) {
    a%=m;
    ll ret = 1;
    while(n)
    {
        if (n&1) ret=ret*a%m;
        a=a*a%m;
        n>>=1;
    }
    return ret;
}
ll f(ll n,ll m)
{
    if (m==1) return 0;
    if (n==1) return 1;
    if (n==2) return 2%m;
    if (n==3) return 9%m;
    if (n==4) return 262144%m;
    return qpow(n,f(n-1,fi(m)) % fi(m) + fi(m),m);
}
int main()
{
    ll n,m;
    while(cin >> n >> m)
    {
        cout << f(n,m) << endl;
    }
    return 0;
}