C - A^n

Contest Duration: 2025-01-26(Sun) 12:00 - 2025-01-26(Sun) 14:00 (local time) (120 minutes) Back to Home

C - A^n - 1 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

$1$ 以上 $10^9$ 以下の正整数 $N$ が与えられます。

以下の条件を共に満たす正整数の組 $(A,M)$ を一つ求めてください。ただし、制約下でそのような正整数の組が必ず存在することが証明できます。

$A,M$ はどちらも $1$ 以上 $10^{18}$ 以下の正整数である。
$A^n-1$ が $M$ の倍数となるような正整数 $n$ が存在し、その最小値は $N$ である。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^4$
$1\le N\le 10^9$
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $T$ 
 $\text{case}_1$ 
 $\text{case}_2$ 
 $\vdots$ 
 $\text{case}_T$

ここで、 $\text{case}_i$ は $i$ 番目のテストケースを意味する。

各テストケースは以下の形式で与えられる。

$N$

出力

それぞれのケースについて、条件を満たす正整数の組 $(A,M)$ を以下の形式で出力せよ。

 $A$   $M$

条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1Copy

Copy

出力例 1Copy

Copy

$\text{case}_1$ について考えます。

例えば $(A,M)=(2,7)$ とすると

$n=1$ のとき： $2^1-1=1$ は $7$ の倍数ではない。
$n=2$ のとき： $2^2-1=3$ は $7$ の倍数ではない。
$n=3$ のとき： $2^3-1=7$ は $7$ の倍数である。

となり、条件を満たす最小の $n$ は $3$ になることが確認できます。したがって、 $(A,M)=(2,7)$ を出力すると正答となります。この他にも、例えば $(A,M)=(100,777)$ などが条件を満たします。

Score : $600$ points

Problem Statement

You are given a positive integer $N$ between $1$ and $10^9$ , inclusive.

Find one pair of positive integers $(A, M)$ satisfying the following conditions. It can be proved that such a pair of integers always exists under the constraints.

Both $A$ and $M$ are positive integers between $1$ and $10^{18}$ , inclusive.
There exists a positive integer $n$ such that $A^n - 1$ is a multiple of $M$ , and the smallest such $n$ is $N$ .

You are given $T$ test cases; solve each of them.

Constraints

$1 \le T \le 10^4$
$1 \le N \le 10^9$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $T$ 
 $\text{case}_1$ 
 $\text{case}_2$ 
 $\vdots$ 
 $\text{case}_T$

Here, $\text{case}_i$ denotes the $i$ -th test case.
Each test case is given in the following format:

$N$

Output

For each test case, print a pair of positive integers $(A, M)$ in the following format:

 $A$   $M$

If there are multiple valid solutions, any one of them is considered correct.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Consider $\text{case}_1$ .

For example, if we choose $(A,M)=(2,7)$ , then:

When $n=1$ : $2^1 - 1 = 1$ is not a multiple of $7$ .
When $n=2$ : $2^2 - 1 = 3$ is not a multiple of $7$ .
When $n=3$ : $2^3 - 1 = 7$ is a multiple of $7$ .

Hence, the smallest $n$ for which $A^n - 1$ is a multiple of $M$ is $3$ . Therefore, $(A,M)=(2,7)$ is a correct solution. Other valid solutions include $(A,M)=(100,777)$ .