P10699 [SNCPC2024] Guess the Prime I

**This is an interactive problem.** MCPlayer542 has a mysterious **odd prime** $p$, but he does not want you to know what it is. He plans to use a function $f(x)$ to encrypt his number. The value of $f(x)$ is the sum of the decimal digits of $x$. For example, $f(5)=5$, $f(542)=5+4+2=11$, and $f(1024)=1+0+2+4=7$. **However, since you are too smart, he thought about it and decided to change the encryption function to:** $$g(x)=f(f(f(f(f(f(f(f(f(f(x))))))))))$$ **That is, apply $f(x)$ continuously $10$ times, and replace the $p$ in his hand with $q=p^k$.** Now he is going to give you $n$ integers $g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})$, and he wants you to tell him what $$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)$$ are, respectively. **He thinks you definitely cannot guess it, so he decides to let you choose $m$ and $a_1,\ a_2,\ \ldots,\ a_n$ yourself.** Can you complete this task? **Note: The range of $m$ has special constraints.**

The input contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 500$), indicating the number of test cases. The interactive process for each test case is described below. In each test case, the first line contains two integers $n$ and $k$ ($1\le n\le 50, \ 1\le k\le 10^9$), separated by a single space, with meanings as described in the statement. Then, for each interaction, output one integer $a_i$ per line ($1\le a_i\le 10^{18},a_i$ **are pairwise distinct**), indicating the exponent of $q$ you want to query. After making a query, you should read an integer, which is $g(q^{a_i})$. After finishing $n$ rounds of interaction, you need to output one integer $m$ in one line ($m\ge 35,1\le m\cdot a_i\le 10^{18}$), then output $n$ numbers in the next line: $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)$, separated by single spaces, as the answer. **You must perform exactly $n$ rounds of interaction, then output the answer and terminate the program, otherwise you may get unpredictable results.** Note that at the end of each output in your program (that is, each time you output $a_i$ for an interaction, and when you finally output $m$ and the answers), you need to print a newline and flush the output buffer. Otherwise, you will get $\text{Idleness Limit Exceeded}$. - In C: $\text{fflush(stdout)}$; - In C++: $\text{cout.flush()}$; - In Java: $\text{System.out.flush()}$; - In Python: $\text{stdout.flush()}$; to flush the output buffer. **It is guaranteed that the odd prime** $p$ ($2

N/A

In the first test case, the odd prime $p=3$ in MCPlayer542's hand, so $q=p^k=3$. We choose the array $a=\{1,\ 2,\ 3\}$, and obtain $g(3^1)=3, \ g(3^2)=9, \ g(3^3)=9$ in order. Then we guess $p=3$ and choose $m=100$, so we output $3^1\bmod (100\times 1)=3, \ 3^2\bmod (100\times 2)=9, \ 3^3\bmod (100\times 3)=27$. In the second test case, the odd prime $p=7$ in MCPlayer542's hand, so $q=p^k=49$. We choose the array $a=\{1,\ 7,\ 49\}$, and obtain $g(49^1)=4,\ g(49^7)=4,\ g(49^{49})=4$ in order. Then we **keenly notice** $p=7$ and choose $m=49$, so we output $49^1\bmod (49\times 1)=0, \ 49^7\bmod (49\times 7)=0, \ 49^{49}\bmod (49\times 49)=0$. Note: The phrase “**keenly notice**” in the second test case is only used as an illustration of the interactive process, and does not guarantee that the above interaction can determine that $p=7$. Translated by ChatGPT 5