UOJ Logo Universal Online Judge

UOJ

#718. 【北大集训2021】算术

附件下载 统计

今天,生活在 14 进制世界的小 Q 学习了一种判断给定的大数是否是 9 的倍数的方法。我们以 $(1BB40)_{14} = (70812)_{10}$ 作为例子描述该方法,下面设 $b=14$,$p=9$,下面的方法中所有的运算在 $b$ 进制下进行。

  1. 从低位往高位,将每个连续的 $k=2$ 位划分为一段。例子中,$(1BB40)_{b}$ 被划分为 $1 \mid BB \mid 40$ 三段。
  2. 从低位往高位从 $0$ 开始给每一段编号。例子中,第 $0$ 段为 $40$,第 $1$ 段为 $BB$,第 $2$ 段为 $1$。
  3. 对于第 $i$ 段计算出值 $b_i$:设第 $i$ 段在 $b$ 进制下的值为 $a_i$,如果 $i$ 为奇数则 $b_i$ 为满足 $(a_i+b_i) \equiv 0(\bmod\ p)$ 的最小非负整数 $b_i$,如果 $i$ 为偶数则 $b_i$ 为满足 $(a_i-b_i) \equiv 0(\bmod\ p)$ 的最小非负整数 $b_i$。例子中有 $b_0=2,b_1=6,b_2=1$。
  4. 将 $b_i$ 按照下标大的在低位,下标小的在高位的顺序顺次拼接,形成一个 $b$ 进制数并输出。例子中输出结果为 $(261)_{b} = (477)_{10}$。容易验证 $477$ 和 $70812$ 都是 $p$ 的倍数。

可以证明上述方法输入和输出的数要么同时是 $p$ 的倍数,要么同时不是 $p$ 的倍数。而且数字的位数变少了,所以多做几次就可以得到一个很小的数,然后就可以简单地判断了。

小 Q 深深地被这个算法吸引了,所以他想给出一个 $b,p$ 不同于 $14,9$ 时的通用方法。但是他发现,当上面的方法中 $b,p$ 的取值变化时,$k$ 不一定等于 $2$:有时会是 $1$,有时会大于 $2$,有时甚至不存在满足条件的 $k$。所以对于给定的 $b,p$,小 Q 想知道在 $b$ 进制下上述方法的第一步中正整数 $k$ 的最小值,使得无论输入如何,输入和对应的输出要么同时是 $p$ 的倍数,要么同时不是 $p$ 的倍数,或者报告这样的 $k$ 不存在。

注意 $p$ 不一定是质数。

输入格式

从标准输入读入数据。

测试点有多组测试数据,保证同一测试点下的 $p$ 相同。输入的第一行包含两个正整数 $T,p$,分别表示该组测试点的测试数据组数与方法的 $p$ 参数。

接下来 $T$ 行每行输入一行一个整数 $b$ 表示每组测试数据的进制。

输入中的所有数字按照十进制给出。

输出格式

输出到标准输出。

对于每组数据输出一行,若不存在合法的 $k$ 输出 -1,否则输出最小的满足条件的正整数 $k$。

样例

input

2 9
14
16

output

2
-1

数据范围与提示

对于所有数据,保证 $1 \le T \le 10^{5},2 \leq p \le 10^{15},2 \leq p < b \leq 10 \times p$。

子任务编号 $2 \leq p \leq$ $1 \leq T \leq$ 分值
$1$ $3$ $10$ $5$
$2$ $10$ $5$
$3$ $10^{2}$ $10^{2}$ $5$
$4$ $10^{4}$ $11$
$5$ $10^{6}$ $11$
$6$ $10^{8}$ $10^{3}$ $11$
$7$ $10^{10}$ $11$
$8$ $10^{12}$ $7$
$9$ $10^{14}$ $10^{4}$ $17$
$10$ $10^{15}$ $10^{5}$ $17$

为了选手们的身心健康,下发文件中的 down.cpp 中实现了大整数取模乘法函数 mul(A, B, P),你需要保证 $A,B \in [0,P-1],P\leq 10^{15}$,函数会返回 $(A \times B) \bmod P$。你可以自由选择使用或者不使用这份代码。

时间限制:2s$\texttt{4s}$

空间限制:$\texttt{512MB}$