分数: 1400 点
问题陈述
处理 Q 查询如下。
- 给你两个整数 A_i 和 M_i。判断是否存在正整数 K_i 不超过 2 × 10^{18} 这样 A_i^{K_i} ≡ K_i (mod M_i),如果存在则查找一个。
约束
- 1 \leq Q \leq 100
- 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
- 1 \leq M_i \leq 10^9(1 \leq i \leq Q)
输入
输入由标准输入按以下格式给出:
Q A_1 M_1 : A_Q M_Q
输出
在 i第行,打印 -1 如果没有整数 K_i 满足条件。 否则,打印一个整数 K_i 不超过 2 × 10^{18} 这样 A_i^{K_i} ≡ K_i (mod M_i)。如果有多个解决方案,则任何一个都将被接受。
示例输入 1
4 2 4 3 8 9 6 10 7
示例输出 1
4 11 9 2
可见满足条件: 2^4 = 16 ≡ 4 (mod 4), 3^{11} = 177147 ≡ 11 (mod 8), 9^9 = 387420489 ≡ 9 (mod 6) 和 10^2 = 100 ≡ 2 (mod 7).
示例输入 2
3 177 168 2028 88772 123456789 987654321
示例输出 2
7953 234831584 471523108231963269