{"problem":{"name":"「SWTR-8」幂塔方程","description":{"content":"如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。 他想让你求解： $$ x ^ x\\equiv D \\pmod n $$ 保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。 你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。 多组测","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8457"},"statements":[{"statement_type":"Markdown","content":"如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。\n\n他想让你求解：\n$$\nx ^ x\\equiv D \\pmod n\n$$\n\n保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。\n\n你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。\n\n多组测试数据。\n\n## Input\n\n第一行一个整数 $S$，表示该测试点的 Subtask 编号。\n\n第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：\n\n- 第一行两个整数 $n, D$。\n- 第二行若干递增的质数 $p_1, p_2, \\cdots, p_k$，表示 $n$ 的所有质因子。\n\n## Output\n\n输出 $T$ 行 $[-1, 2 ^ {125}]$ 范围内的整数。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/iflu3244.png)\n\n图片来自于 Solara570 的 B 站视频 [轻易相信简单直观的结论究竟有多危险？](https://www.bilibili.com/video/BV1PW41177Vb)。\n\n很久以前的某一天，小 A 在 B 站上无意间刷到了这个视频。视频中的无穷幂塔方程及其「简单直观，但暗藏陷阱」的解法令他影响深刻。\n$$\n\\Huge x ^ {x ^ {x ^ {x ^ {x}}}}\n$$\n\n## Note\n\n**「数据范围与约定」**\n\n**本题采用捆绑测试**。\n\n- Subtask #1（5 points）：$n\\leq 20$。\n- Subtask #2（8 points）：$n\\leq 400$。依赖 Subtask #1。\n- Subtask #3（11 points）：$n$ 是质数，$T\\leq 10 ^ 4$。\n- Subtask #4（15 points）：$\\mu(n) \\neq 0$，$T\\leq 100$。\n- Subtask #5（9 points）：$\\mu(n) \\neq 0$，$T\\leq 10 ^ 4$。依赖 Subtask #4。\n- Subtask #6（13 points）：$n = p ^ k(p \\in \\mathrm{prime})$，$T\\leq 100$。\n- Subtask #7（7 points）：$n = p ^ k(p \\in \\mathrm{prime})$，$T\\leq 10 ^ 4$。依赖 Subtask #3，#6。\n- Subtask #8（6 points）：$n$ 的最大质因子不超过 $ 1064$。依赖 Subtask #2。\n- Subtask #9（16 points）：$n\\leq 10 ^ 9$，$T\\leq 10 ^ 4$。\n- Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。\n\n对于 $100\\%$ 的数据：\n\n- $1\\leq T\\leq 4\\times 10 ^ 4$。\n- $2\\leq n \\leq 10 ^ {18}$。\n- $1\\leq D < n$，$D\\perp n$。\n- $2\\leq p_1 < p_2 < \\cdots < p_k \\leq 10 ^ 5$。\n\n**「帮助与提示」**\n\n选手可以通过边读入边试除的方式判断何时停止读入 $n$ 的质因子。\n\n**「题目来源」**\n\n- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) F\n- Idea & Solution：[demonlover923](https://www.luogu.com.cn/user/152997) & [codecode](https://www.luogu.com.cn/user/119526)。\n- Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294)。\n\n**Update on 2025.5.30**：本题可以做 $p_k\\leq 10 ^ {18}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8457","tags":["原根","数论","洛谷原创","Special Judge","O2优化","扩展欧几里德算法","中国剩余定理 CRT","逆元","洛谷月赛"],"sample_group":[["0\n10\n7 4\n7\n16 3\n2\n6 1\n2 3\n144 5\n2 3\n2520 11\n2 3 5 7\n999999 2\n3 7 11 13 37\n22511 21795\n22511\n47067727606562827 30911969774113407\n3083 13697 25747 43291\n2147483648 2333333\n2\n675288511488360000 510472780110265817\n2 3 5 7 11","25\n11\n1\n101\n4811\n219871229\n16139671\n760913896873844308082367046696111\n1221598821\n24445987958110300438937\n"]],"created_at":"2026-03-03 11:09:25"}}