問題一覧 > 通常問題

No.1498 Factorization from -1 to 1

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : sgswsgsw
0 ProblemId : 6429
問題文最終更新日: 2021-05-04 00:25:09

問題文

最近、そぬけさんはエラトステネスのふるいを勉強しました。
その結果、自然数列 $S_i = i (1 \le i \le 100000)$ を素早く素因数分解することができるようになりました。
しかし、それだけでは面白くないので、少し変わった整数列に対しても素因数分解を試みようと考えました。

初めに、$A_i = i^2  ( 1 \le i \le 100000)$ の素因数分解について考えてみました。そぬけさんはすぐいいアイデアを思いつきました。
次に、 $B_i = i^2-1 ( 1 \le i \le 100000)$ の素因数分解について考えてみました。これも、そぬけさんはすぐに解くことができました。
最後に、$X_i = i^2+1 ( 1 \le i \le$ 100000$100001)$ の素因数分解について考えてみたのですが、

そぬけさんはこの数列の一般項$X_i$は前の二つと違い、きれいに因数分解できない形であることに気づきました。
このままではそぬけさんは$X_i$の値がとても大きくなった時の因数分解ができないので、どう素因数分解すれば良いのか困ってしまいました。
そぬけさんの代わりに$X_i(1 \le i \le$ 100000$100001)$の素因数分解を行ってあげてください。

入力

$Q$
$q_1$
$q_2$
.
.
.
$q_Q$

初めに、前入力の個数$Q$が与えられる。
ここに、$Q$は自然数かつ$1 \le Q \le 100000$をみたす。
その後、続いて$i(1 \le i \le Q)$行にわたって、自然数$q_i(1 \le q_i \le $100000 $100001)$が入力される。
条件に不備がありましたので取り消し線で修正を加えました。申し訳ありません。

出力

$Q$行にわたって出力してください。 $i(1 \le i \le Q)$行目には、$X_{q_i}$の素因数分解の結果を出力してください。
この時、各項の素因数分解の結果は、その数が持つ素因数を重複も含めて小さい順に並べて出力してください。 入出力に関しては、以下の例も参考にしてください。
また、最後に改行してください。

サンプル

サンプル1
入力
8
3
1
4
1
5
9
2
6
出力
2 5
2
17
2
2 13
2 41
5
37

$X_3$ = $3^2 + 1 = 10 = 2 * 5 $です。
$X_1$ = $1^2 + 1 = 2 $です。
$X_4$ = $4^2 + 1 = 17 $です。
$X_1$ = $1^2 + 1 = 2 $です。
$X_5$ = $5^2 + 1 = 26 = 2 * 13 $です。
$X_9$ = $9^2 + 1 = 82 = 2 * 41 $です。
$X_2$ = $2^2 + 1 = 5 $です。
$X_6$ = $6^2 + 1 = 37 $です。

サンプル2
入力
5
8523
6189
6365
1311
37
出力
2 5 13 558781
2 29 660409
2 13 1558201
2 859361
2 5 137

各項の素因数分解の結果は、その数が持つ素因数を小さい順に並べて出力することに注意してください。

サンプル3
入力
20
40887
72874
61303
51575
67282
63799
77986
73719
58829
55758
29693
85015
65766
31202
47690
25980
91221
41077
83153
79062
出力
2 5 181 923617
5310619877
2 5 13 37 781301
2 2437 545749
5 5 17 1601 6653
2 13 156550477
53 114751249
2 1321 2056961
2 29 29 269 7649
5 621790913
2 5 5 5 41 86017
2 13 4801 57901
51637 83761
5 194712961
3457 657893
17 37 1073069
2 11909 349369
2 5 461 366013
2 5 13 113 470689
5 1250159969

$5310619877$という、巨大な素数だけを因数にもつ項も存在するようです。そぬけさんには難しいかもしれません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。