P8993 [Peking University Training 2021] Arithmetic.

CTT2021 D4T1.

Today, Xiao Q, who lives in a base-$14$ world, learned a method to determine whether a given big integer is a multiple of $9$. We use $(1BB40)_{14} = (70812)_{10}$ as an example to describe this method. Let $b=14$ and $p=9$. All operations in the method below are performed in base $b$. 1. From the least significant digit to the most significant digit, split the number into blocks, each consisting of $k=2$ consecutive digits. In the example, $(1BB40)_{b}$ is split into three blocks: $1 \mid BB \mid 40$. 2. From the least significant block to the most significant block, number each block starting from $0$. In the example, block $0$ is $40$, block $1$ is $BB$, and block $2$ is $1$. 3. Compute a value $b_i$ for block $i$: let the value of block $i$ in base $b$ be $a_i$. If $i$ is odd, then $b_i$ is the smallest non-negative integer such that $(a_i+b_i) \equiv 0 \pmod p$. If $i$ is even, then $b_i$ is the smallest non-negative integer such that $(a_i-b_i) \equiv 0 \pmod p$. In the example, $b_0=2$, $b_1=6$, and $b_2=1$. 4. Concatenate the $b_i$ values in order **with larger indices in lower digits and smaller indices in higher digits**, forming a base-$b$ number, and output it. In the example, the output is $(261)_{b} = (477)_{10}$. It is easy to verify that both $477$ and $70812$ are multiples of $p$. It can be proven that the input and output numbers produced by the method above are either both multiples of $p$, or both not multiples of $p$. Also, the number of digits becomes smaller, so by repeating this process several times you can obtain a very small number, and then you can check it easily. Xiao Q was deeply attracted by this algorithm, so he wants to give a general method for $b,p$ different from $14,9$. However, he found that when the values of $b,p$ change, $k$ in Step 1 is not necessarily $2$: sometimes it is $1$, sometimes it is greater than $2$, and sometimes there is no $k$ that satisfies the requirement at all. Therefore, for given $b$ and $p$, Xiao Q wants to know the minimum **positive integer** $k$ in Step 1 (in base $b$), such that no matter what the input is, the input and the corresponding output are either both multiples of $p$, or both not multiples of $p$, or report that such a $k$ does not exist. Note that $p$ is not necessarily a prime number.

There are multiple test cases in the testdata. It is guaranteed that within the same test point, $p$ is the same. The first line contains two positive integers $T,p$, with $1 \le T \le 10^5$ and $2 \leq p \le 10^{15}$, representing the number of test cases and the parameter $p$ of the method. The next $T$ lines each contain one integer $b$, representing the base for each test case. It is guaranteed that $2 \leq p < b \leq 10 \times p$. **All numbers in the input are given in decimal.**

For each test case, output one line. If no valid $k$ exists, output `-1`; otherwise, output the minimum **positive integer** $k$ that satisfies the condition.

| Subtask ID | $2\leq p\leq$ | $1\leq T\leq$ | Score | | :--------: | :-----------: | :-----------: | :--: | | $1$ | $3$ | $10$ | $5$ | | $2$ | $10$ | $10$ | $5 $ | | $3$ | $10^2$ | $10^2$ | $5$ | | $4$ | $10^4$ | $10^2$ | $11$ | | $5$ | $10^6$ | $10^2$ | $11 $ | | $6$ | $10^8$ | $10^3$ | $11$ | | $7$ | $10^{10}$ | $10^3$ | $11 $ | | $8$ | $10^{12}$ | $10^3$ | $7$ | | $9$ | $10^{14}$ | $10^4$ | $17$ | | $10$ | $10^{15}$ | $10^5$ | $17 $ | For the physical and mental health of contestants, the distributed file provides a big-integer modular multiplication function `mul(A, B, P)` implemented in `down.cpp`. You need to ensure $A,B \in [0,P-1]$, and the function will return $(A \times B) \bmod P$. You may choose to use or not use this code freely. **When calling it, you must ensure that $A,B,P$ are all no greater than $10^{15}$.** Translated by ChatGPT 5