2144 . 喔踢貓

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯，道歉！$

User's AC Ratio

78.7% (48/61)

Submission's AC Ratio

33.8% (94/278)

Tags

Description

有一隻貓，叫做喔踢。她因為在背地裡對N老大不利，某天被N老大的騎士團抓到，而遭受慘無人道的酷刑...

「求求你別再考我了...」喔踢貓如此哀號道。

精神及肉體受到打擊的她，轉向警察局求助。背ㄍ...不是，根據喔踢貓的敘述，已知K騎士團中連續的團員們相乘（K團員們是自然數），會剛好是N老大的倍數。由於你不能濫抓無辜百姓，所以只能抓最少的K，來找到N老大。

以上敘述想講的是，請找到最小的K，使得K!是N的倍數。
註：0! = 1

Input Format

第一行輸入一個數字 Q
接著有Q行，每行輸入一個數字N
$( N \leq 5 \times 10 ^ 6, Q \leq 2 \times 10 ^ 5)$

Output Format

輸出能找到N老大，所需要的最少K團員數量。
也就是輸出最小的K使得K!是N的倍數。

Sample Input 1

4
1
8
13
169

Sample Output 1

0
4
13
26

Hints

Problem Source

Problem Set by jeeeerrrpop

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N\leq 1000, Q \leq 1000$ 10
2 5~9 $N\leq 1000$ 20
3 10~15 $N \leq 2 \times 10 ^ 6 $ 57
4 16 無額外限制 13

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 3
11 1000 262144 65536 3
12 1000 262144 65536 3
13 1000 262144 65536 3
14 1000 262144 65536 3
15 1000 262144 65536 3
16 1000 262144 65536 4
Submit
Status
Ranklist
Back to Top