which is already pretty big. Note that exponentiation is right-associative: 
.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; }
原文：https://www.cnblogs.com/tetew/p/9748274.html