QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+1]

# 3278. 算术

Statistics

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

  1. 从低位往高位,将每个连续的 k=2 位划分为一段。例子中,(1BB40)b 被划分为 1BB40 三段。
  2. 从低位往高位从 0 开始给每一段编号。例子中,第 0 段为 40,第 1 段为 BB,第 2 段为 1
  3. 对于第 i 段计算出值 bi:设第 i 段在 b 进制下的值为 ai,如果 i 为奇数则 bi 为满足 (ai+bi)0(mod 的最小非负整数 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}。容易验证 47770812 都是 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。你可以自由选择使用或者不使用这份代码。