#2061. 算术
算术
算术
题目描述
标题: 算术 - Problem - QOJ.ac
#3278. 算术
今天,生活在 14 进制世界的小 Q 学习了一种判断给定的大数是否是 9 的倍数的方法。我们以 (1BB40)14=(70812)10 作为例子描述该方法,下面设 b=14,p=9,下面的方法中所有的运算在 b 进制下进行。
- 从低位往高位,将每个连续的 k=2 位划分为一段。例子中,(1BB40)b 被划分为 1∣BB∣40 三段。
- 从低位往高位从 0 开始给每一段编号。例子中,第 0 段为 40,第 1 段为 BB,第 2 段为 1。
- 对于第 i 段计算出值 bi:设第 i 段在 b 进制下的值为 ai,如果 i 为奇数则 bi 为满足 (ai+bi)≡0(mod p) 的最小非负整数 bi,如果 i 为偶数则 bi 为满足 (ai−bi)≡0(mod p) 的最小非负整数 bi。例子中有 b0=2,b1=6,b2=1。
- 将 bi 按照下标大的在低位,下标小的在高位的顺序顺次拼接,形成一个 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≤T≤105,2≤p≤1015,2≤p<b≤10×p。
子任务编号 2≤p≤ 1≤T≤ 分值 1 3 10 5 2 10 5 3 102 102 5 4 104 11 5 106 11 6 108 103 11 7 1010 11 8 1012 7 9 1014 104 17 10 1015 105 17
为了选手们的身心健康,下发文件中的 down.cpp 中实现了大整数取模乘法函数 mul(A, B, P),你需要保证 A,B∈[0,P−1],P≤1015,函数会返回 (A×B)modP。你可以自由选择使用或者不使用这份代码。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 9
14
16
2
-1