P8457 「SWTR-8」幂塔方程

 图片来自于 Solara570 的 B 站视频 [轻易相信简单直观的结论究竟有多危险？](https://www.bilibili.com/video/BV1PW41177Vb)。 很久以前的某一天，小 A 在 B 站上无意间刷到了这个视频。视频中的无穷幂塔方程及其「简单直观，但暗藏陷阱」的解法令他影响深刻。 $$ \Huge x ^ {x ^ {x ^ {x ^ {x}}}} $$

如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。 他想让你求解： $$ x ^ x\equiv D \pmod n $$ 保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。 你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。 多组测试数据。

无

无

**「数据范围与约定」** **本题采用捆绑测试**。 - Subtask #1（5 points）：$n\leq 20$。 - Subtask #2（8 points）：$n\leq 400$。依赖 Subtask #1。 - Subtask #3（11 points）：$n$ 是质数，$T\leq 10 ^ 4$。 - Subtask #4（15 points）：$\mu(n) \neq 0$，$T\leq 100$。 - Subtask #5（9 points）：$\mu(n) \neq 0$，$T\leq 10 ^ 4$。依赖 Subtask #4。 - Subtask #6（13 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 100$。 - Subtask #7（7 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 10 ^ 4$。依赖 Subtask #3，#6。 - Subtask #8（6 points）：$n$ 的最大质因子不超过 $ 1064$。依赖 Subtask #2。 - Subtask #9（16 points）：$n\leq 10 ^ 9$，$T\leq 10 ^ 4$。 - Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。 对于 $100\%$ 的数据： - $1\leq T\leq 4\times 10 ^ 4$。 - $2\leq n \leq 10 ^ {18}$。 - $1\leq D < n$，$D\perp n$。 - $2\leq p_1 < p_2 < \cdots < p_k \leq 10 ^ 5$。 **「帮助与提示」** 选手可以通过边读入边试除的方式判断何时停止读入 $n$ 的质因子。 **「题目来源」** - [Sweet Round 8](https://www.luogu.com.cn/contest/73382) F - Idea & Solution：[demonlover923](https://www.luogu.com.cn/user/152997) & [codecode](https://www.luogu.com.cn/user/119526)。 - Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294)。