首先考虑扩展欧拉定理的经典题目 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)。