115 . 倒數循環節

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

kenkenken
Caidorz

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

30.2% (26/86)

Tags

ioicamp ioicamp-2023

Description

小叮和小咚最近合資開了一家甜點店！其中，最受歡迎的非蛋糕莫屬：小叮負責考蛋糕，然後小咚負責將烤好的蛋糕切成 N 等份，然後在黑板上面寫上蛋糕的價格。一個蛋糕總共要賣一塊錢，所以理所當然一份蛋糕的價錢就是 1/N 啦！但是，小咚對於價格是很有想法的：她要求價格一定可以完全循環！她所謂的完全循環小數指的就是小數不只要循環，而且小數點後就馬上開始循環，不會一開始先有一小段再開始循環。舉例來說：

  • 1/2=0.5,1/5=0.2 並不是完全循環小數，因為它們不循環；
  • 1/6=1.16― 也不是個完全循環小數，因為它一開始有一個 1，那個 1 並不循環。同樣地，1/14=0.07142857142...=0.07142857― 也不是，因為其前面有不循環的 0.07；
  • 1/3=0.3―,1/7=0.142857― 都是完全循環小數。

現在，給定一個蛋糕要切成 N 分，小咚想要請你/妳寫一個程式判斷其價格是否為完全循環小數 —— 如果是的話，也請判斷其循環節長度。舉例來說，0.7122― 的循環節長度是 4。此外，因為他們的生意實在太好了，所以有 Q 個蛋糕的資料要處理。

Input Format

第一行是一個數字 Q，代表有幾個蛋糕的資料要處理。

接下來的 Q 行中的第 i 行有一個正整數 Ni 代表第 i 份蛋糕要切成幾等份。

  • 1≤Q≤106
  • 1≤Ni≤106

在 subtasks 欄位中，N=max1≤i≤QNi。

Output Format

對於每一個蛋糕，如果 1/Ni 是完全循環小數，則請輸出其循環節；否則請輸出 −1。

注意：若一個小數有多種表示方式（例：1/4=0.25=0.249―），我們取結尾都是 0 的那個。

Sample Input 1

4
1
2
3
7121

Sample Output 1

-1
-1
1
3560

Sample Input 2

6
23
29
1201
787
7122
317

Sample Output 2

22
28
200
393
-1
79

Hints

Problem Source

IOICamp 2023 Day3 pG

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~8 NQ≤106 14
3 0~1, 9~17 N,Q≤105 33
4 0~21 無額外限制 53

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4
1 2000 524288 65536 1 2 3 4
2 2000 524288 65536 2 4
3 2000 524288 65536 2 4
4 2000 524288 65536 2 4
5 2000 524288 65536 2 4
6 2000 524288 65536 2 4
7 2000 524288 65536 2 4
8 2000 524288 65536 2 4
9 2000 524288 65536 3 4
10 2000 524288 65536 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 3 4
18 2000 524288 65536 4
19 2000 524288 65536 4
20 2000 524288 65536 4
21 2000 524288 65536 4
Submit
Back to Top