テトレーションという単語を初めて聞いた。
http://yukicoder.me/problems/472
問題
を以下の計算を行う演算子とする。
A,N,Mに対しを求めよ。
解法
自分では全く手が出なかったのでEditorialを参考に解いた。
以下ほとんどEditorialそのまま。若干実装について補足した。
とする。求めたいのはである。
を用いると以下のように書ける。
ここで自体は64bit値で収まらないほど大きいが、modpowの周期性を用いることでを求めることはできる。
modpowの周期はオイラー関数なので、ならそのままmodpowを計算すればよいし、そうでないなら
を求めればよい。
再帰的にHが出てくるが、第3項がになるので再帰のたびに減少し、実際は再帰の回数はさほど大きくない。
残る問題はの計算と、がm以下かどうかの判定である。
は蟻本にあるとおりm以下でmと互いに素な自然数の個数なので、m回GCDを計算すれば求められる。
は厳密に求めるのは大きすぎて困難だが、以下の事実からmを超えるかどうかは判定できる。
- a==1なら1
- a>1の場合
- n==0なら1
- n==1ならa
- n==2ならa^aなので、aが16までなら2^64以下に収まる。
- n==3かつa=2なら2^2^2=16
- n==3かつa=3なら3^3^3=7625597484987
- n==4かつaが2なら2^2^2^2=65535
- それ以外なら2^64に収まらない
ll A,N,M; ll modpow(ll a, ll n, ll mo) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } const int Mmax=2000; int phi[Mmax+20]; // return min(upbound,A^^B) ll AtB(ll a,ll b,ll upbound) { if(b==0 || a==1) return min(upbound,1LL); if(b==1) return min(upbound,a); if(b==2) return (a>10)?upbound:min(modpow(a,a,1LL<<60),upbound); if(a==2 && b==3) return min(upbound,1LL<<4); if(a==3 && b==3) return min(upbound,modpow(3,27,1LL<<60)); if(a==2 && b==4) return min(upbound,1LL<<16); return upbound; } ll H4M(ll a,ll b,ll m) { if(m==1) return 0; if(a==1 || b==0) return 1; ll t=AtB(a,b-1,m+1); if(t<=m) return modpow(a,t,m); return modpow(a,m + (H4M(a,b-1,phi[m])-m)%phi[m], m); } void GetPhi() { int i,x; for(x=1;x<=Mmax;x++) for(i=1;i<=x;i++) phi[x]+=__gcd(i,x)==1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>A>>N>>M; GetPhi(); cout<< H4M(A,N,M) << endl; }
まとめ
この式変形は難しいなぁ…。