/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
n^n を 10^9 で割った余りが X となるような正の整数 n が存在するか判定し、存在する場合は最小のものを求めてください。
Q 個のテストケースが与えられるので、それぞれに対して答えてください。
制約
- 1 \leq Q \leq 10000
- 1 \leq X \leq 10^9 - 1
- X は 2 の倍数でも 5 の倍数でもない
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。ただし、i 個目 (1 \leq i \leq Q) のテストケースにおける X の値を X_i とします。
Q X_1 X_2 \vdots X_Q
出力
Q 行にわたって出力してください。i 行目には、i 個目のテストケースに対する答えを出力してください。ただし、条件を満たす n が存在しない場合は答えを -1 とします。
入力例 1
2 27 311670611
出力例 1
3 11
この入力例は 2 個のテストケースからなります。
- 1 個目：3^3 = 27 を 10^9 で割った余りは 27 なので、n = 3 で条件を満たします。
- 2 個目：11^{11} = 285311670611 を 10^9 で割った余りは 311670611 なので、n = 11 で条件を満たします。
Score: 800 points
Problem Statement
Determine whether there is a positive integer n such that the remainder of n^n divided by 10^9 is X. If it exists, find the smallest such n.
You will be given Q test cases to solve.
Constraints
- 1 \leq Q \leq 10000
- 1 \leq X \leq 10^9 - 1
- X is neither a multiple of 2 nor a multiple of 5.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where X_i is the value of X in the i-th test case (1 \leq i \leq Q):
Q X_1 X_2 \vdots X_Q
Output
Print Q lines. The i-th line should contain the answer for the i-th test case. If no n satisfies the condition, the answer should be -1.
Sample Input 1
2 27 311670611
Sample Output 1
3 11
This sample input consists of two test cases.
- The first case: The remainder of 3^3 = 27 divided by 10^9 is 27, so n = 3 satisfies the condition.
- The second case: The remainder of 11^{11} = 285311670611 divided by 10^9 is 311670611, so n = 11 satisfies the condition.