2144 . 喔踢貓

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

81.2% (52/64)

Submission's AC Ratio

35.8% (105/293)

Tags

CKsim 2019-CKsim

Description

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

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

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

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

Input Format

第一行輸入一個數字 Q
接著有Q行，每行輸入一個數字N
(N≤5×106,Q≤2×105)

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≤1000,Q≤1000 10
2 5~9 N≤1000 20
3 10~15 N≤2×106 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
Back to Top