#P8993. [北大集训 2021] 算术

[北大集训 2021] 算术

题目背景

CTT2021 D4T1

题目描述

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

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

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

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

注意 pp 不一定是质数。

输入格式

测试点有多组测试数据,保证同一测试点下的 pp 相同。输入的第一行包含两个正整数 T,pT,p,保证 1T1051 \le T \le 10^52p10152 \leq p \le 10^{15},分别表示该组测试点的测试数据组数与方法的 pp 参数。

接下来 TT 行每行输入一行一个整数 bb 表示每组测试数据的进制。保证 2p<b10×p2 \leq p < b \leq 10 \times p

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

输出格式

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

2 9
14
16
2
-1

提示

子任务编号 2p2\leq p\leq 1T1\leq T\leq 分值
11 33 1010 55
22 1010 55
33 10210^2 10210^2 55
44 10410^4 1111
55 10610^6 1111
66 10810^8 10310^3 1111
77 101010^{10} 1111
88 101210^{12} 77
99 101410^{14} 10410^4 1717
1010 101510^{15} 10510^5 1717

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