题解：AT_tenka1_2017_f ModularPowerEquation!!

限于作者比较蒻，看完几篇题解后想了很久才想懂······ 感觉目前的几篇题解讲的不是太模糊就是太冗杂，故也在此记录一下自己的想法。

首先考虑扩展欧拉定理的经典题目 P4139 中的结论：一个数 $x$ 的迭代幂次（又称幂塔）$\underbrace {x^{x^{x^{\dots}}}}_{共n个x}=x \uparrow\uparrow n$ 在 $n$ 足够大时满足 $x \uparrow\uparrow n \equiv x \uparrow\uparrow (n+1) \pmod m$，于是设 $k = A \uparrow\uparrow n$，那么根据刚刚的性质就能得到 $A^k \equiv k \pmod{m}$，故如果我们暂不考虑 $k$ 大小的限制，$k$ 自己就是一个合法的答案。但是显然这个 $k$ 可能会很大，于是我们考虑通过 $k$ 构造出符合题意的更小合法解 $k'$ 满足 $A^k \equiv A^{k'} \equiv k \equiv k' \pmod{m}$。

由于 $k$ 是 $A$ 的幂次，而缩小幂次数量级的一个经典方法就是运用扩展欧拉定理，于是假若 $k > \varphi(m)$，根据扩展欧拉定理，我们可以很容易地由上面的条件推导出：如果 $k'$ 同时满足 $A^{k \bmod \varphi(m) \ + \ \varphi(m)} \equiv A^{k'} \pmod{m}$ 与 $k \equiv k' \pmod {m}$，则 $k'$ 符合条件。而前一个式子在 $k' > \varphi(m)$ 时可以由 $k \equiv k' \pmod{\varphi(m)}$ 推导得出（具体证明可设 $r=k \bmod \varphi(m)=k' \bmod \varphi(m)$，那么 $A^{r} \equiv A^{k \bmod \varphi(m)} \equiv A^{k' \bmod \varphi(m)} \pmod{m}$，于是 $A^{k \bmod \varphi(m) \ + \ \varphi(m)} \equiv A^{k' \bmod \varphi(m) \ + \ \varphi(m)} \equiv A^{k'} \pmod{m}$），于是我们的问题最终转化为：求解线性同余方程组 $\begin{cases} k' \equiv k \pmod{\varphi(m)} \\ k' = k \pmod{m} \end{cases}$ 的一组大于 $\varphi(m)$ 的解或判定无解。求解 $k \bmod \varphi(m)$ 以及 $k \bmod m$ 在 $n$ 足够大时的值是可以用 P4139 中同样的做法来做的，而求解线性同余方程组则是 ExCRT 的经典应用，于是整道题就做完了。

对于每次询问，求欧拉函数值的时间复杂度为 $O(\sqrt{m})$，对 $A \uparrow \uparrow n$ 求余的时间复杂度为 $O(\log m)$，故整个程序的总时间复杂度为 $O(Q\sqrt{m}\log m)$。