E - Last 9 Digits

Contest Duration: 2024-02-18(Sun) 12:00 - 2024-02-18(Sun) 14:00 (local time) (120 minutes) Back to Home

E - Last 9 Digits Editorial

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$ とします。

入力例 1Copy

Copy

2
27
311670611

出力例 1Copy

Copy

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 1Copy

Copy

2
27
311670611

Sample Output 1Copy

Copy

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.