実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1400 点
問題文
以下の Q 個のクエリに答えてください。
整数 A_i,M_i が与えられます。A_i^{K_i} ≡ K_i(mod M_i) なる 2 × 10^{18} 以下の正整数 K_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 行目には、i 個目のクエリに対し、問題文の条件を満たす K_i が存在しないなら、-1 を出力せよ。 そうでない場合、A_i^{K_i} ≡ K_i(mod M_i) なる 2 × 10^{18} 以下の正整数 K_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
Score : 1400 points
Problem Statement
Process the Q queries below.
- You are given two integers A_i and M_i. Determine whether there exists a positive integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i), and find one if it exists.
Constraints
- 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)
Inputs
Input is given from Standard Input in the following format:
Q A_1 M_1 : A_Q M_Q
Outputs
In the i-th line, print -1 if there is no integer K_i that satisfies the condition. Otherwise, print an integer K_i not exceeding 2 × 10^{18} such that A_i^{K_i} ≡ K_i (mod M_i). If there are multiple solutions, any of them will be accepted.
Sample Input 1
4 2 4 3 8 9 6 10 7
Sample Output 1
4 11 9 2
It can be seen that the condition is satisfied: 2^4 = 16 ≡ 4 (mod 4), 3^{11} = 177147 ≡ 11 (mod 8), 9^9 = 387420489 ≡ 9 (mod 6) and 10^2 = 100 ≡ 2 (mod 7).
Sample Input 2
3 177 168 2028 88772 123456789 987654321
Sample Output 2
7953 234831584 471523108231963269