Tenka1 Programmer Contest 2017 F - ModularPowerEquation!!

なんだこり

$A^x\equiv x(\mathrm{mod}\varphi (m))\Rightarrow A^{A^x}\equiv A^x(\mathrm{mod}m)$

に気がつくと、$A^{A^{A^{A^A}}}$ みたいなのが答えの一つであることがわかります。（気づくの不可能では？）

これはテトレーションと呼ばれています

judge.yosupo.jp

ライブラリを貼ります

非自明ポイントとして $p=\mathrm{t}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(a,100)mod\varphi (m)$ の値と $q=\mathrm{t}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(a,100)modm$ の値を求める必要があります

（mod を取ったせいで $A^q\equiv q(\mathrm{mod}m)$ とは限らないので、$q+mt\equiv p(\mathrm{mod}\varphi (m))$ となるような $t$ を見つける必要がある、逆に $x=q+mt$ がこの二つの条件を満たしていれば、$A^x\equiv x(\mathrm{mod}m)$ であることもわかる）

補足

$x=\mathrm{t}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}(a,100)$ とします

前述の議論より、 $A^x\equiv x(\mathrm{mod}m)$ です

任意の $s\ge 1$ について $A^{p+s\varphi (m)}\equiv A^x\equiv x(\mathrm{mod}m)$ です

あとは $p+s\varphi (m)\equiv x\equiv q(\mathrm{mod}m)$ であればよいです

これは中国剰余定理で求められます

これ公式解説そのままでは？