P10699 [SNCPC2024] 猜质数 I

**这是一道交互题。** MCPlayer542 手上有一个神秘的**奇质数** $p$，但他并不想让你知道这个数是多少。 他打算用一个函数 $f(x)$ 来加密他的数，其值为 $x$ 在十进制下的各位数字之和，例如 $f(5)=5$，$f(542)=5+4+2=11$，$f(1024)=1+0+2+4=7$。 **然而考虑到你太聪明，他想了想，决定把加密函数改成：** $$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$ **即连续应用 $10$ 次 $f(x)$，并把手上的 $p$ 换成了 $q=p^k$。** 现在他准备给你 $n$ 个整数 $g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$，并希望你能告诉他 $$q^{a_1}\bmod (m\cdot a_1),\ q^{a_2}\bmod (m\cdot a_2),\ \ldots,\ q^{a_n}\bmod (m\cdot a_n)$$ 分别是多少。**他觉得你肯定猜不到，所以决定让你自己选择 $m$ 和 $a_1,\ a_2,\ \ldots,\ a_n$**。你能完成这个任务吗？ **注意：$m$ 的范围有特殊限制。**

无

无

在第一组数据中，MCPlayer542 手上的奇质数 $p=3$，因此有 $q=p^k=3$。 我们选择数组 $a=\{1,\ 2,\ 3\}$，依次得到 $g(3^1)=3, \ g(3^2)=9, \ g(3^3)=9$。 随后我们猜到 $p=3$，选择 $m=100$，因此输出 $3^1\bmod (100\times 1)=3, \ 3^2\bmod (100\times 2)=9, \ 3^3\bmod (100\times 3)=27$。 在第二组数据中，MCPlayer542 手上的奇质数 $p=7$，因此有 $q=p^k=49$。 我们选择数组 $a=\{1,\ 7,\ 49\}$，依次得到 $g(49^1)=4,\ g(49^7)=4,\ g(49^{49})=4$。 随后我们**敏锐地发现** $p=7$，选择 $m=49$，因此输出 $49^1\bmod (49\times 1)=0, \ 49^7\bmod (49\times 7)=0, \ 49^{49}\bmod (49\times 49)=0$。 注：第二组数据中的“**敏锐地发现**”仅作为交互流程的示意，并不保证上述交互可以确定 $p=7$。