問題一覧 > 通常問題

No.1498 Factorization from -1 to 1

レベル : / AI推定難易度 : 1575 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : sgsw
お気に入りにしたユーザー ProblemId : 6429 / 自分の提出
問題文最終更新日: 2021-05-04 00:25:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

Recently, Sonuke studied the sieve of Eratosthenes.
As a result, Sonuke became able to quickly compute the prime factorization of the sequence of natural numbers $S_i = i (1 \le i \le 100000)$.
However, that alone is not very interesting, so Sonuke decided to try prime factorization on some slightly unusual integer sequences as well.

First, Sonuke considered the prime factorization of $A_i = i^2  ( 1 \le i \le 100000)$. Sonuke immediately came up with a good idea.
Next, Sonuke considered the prime factorization of $B_i = i^2-1 ( 1 \le i \le 100000)$. Sonuke was able to solve this one right away too.
Finally, Sonuke considered the prime factorization of $X_i = i^2+1 ( 1 \le i \le$ 100000$100001)$, but

Sonuke noticed that the general term $X_i$ of this sequence, unlike the previous two, is not in a form that factors neatly.
As things stand, Sonuke cannot factorize $X_i$ when its value becomes very large, and is at a loss as to how to compute the prime factorization.
Please compute the prime factorization of $X_i(1 \le i \le$ 100000$100001)$ on Sonuke's behalf.

Input

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

First, the total number of inputs $Q$ is given.
Here, $Q$ is a natural number satisfying $1 \le Q \le 100000$.
Then, over the following $i(1 \le i \le Q)$ lines, natural numbers $q_i(1 \le q_i \le $100000 $100001)$ are given.
There was an error in the constraints, so a correction has been made using strikethrough. We apologize.

Output

Output $Q$ lines. On the $i(1 \le i \le Q)$-th line, output the result of the prime factorization of $X_{q_i}$.
Here, for the prime factorization of each term, output the prime factors of that number, including duplicates, in ascending order. For the input and output, also refer to the examples below.
Also, print a newline at the end.

Sample

Sample 1
Input
8
3
1
4
1
5
9
2
6
Output
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 $.

Sample 2
Input
5
8523
6189
6365
1311
37
Output
2 5 13 558781
2 29 660409
2 13 1558201
2 859361
2 5 137

Note that for the prime factorization of each term, the prime factors of that number must be output in ascending order.

Sample 3
Input
20
40887
72874
61303
51575
67282
63799
77986
73719
58829
55758
29693
85015
65766
31202
47690
25980
91221
41077
83153
79062
Output
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

It seems there are terms whose only factor is a huge prime, such as $5310619877$. This may be difficult for Sonuke.

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