TopCoder

Thumb 971fdce095f74293b40c91b83175a199 400x400
Shaman
初級珂學家

User's AC Ratio

100.0% (11/11)

Submission's AC Ratio

61.5% (32/52)

Tags

Description

又到了一年一度的百貨周年慶時間,每到週年慶,大特價拍賣活動總是伴隨而來,

每次都會吸引一堆男女老少前往瘋狂搶購眾特價商品,

這次,CK 百貨公司為了因應 $110$ 週年慶,決定舉辦一個前所未有的活動,

沒錯,正是獎品大放送的活動,但是這樣還不夠,

大放送的竟然是 $110$ 台汽車!!!!!

這實在是太讓人震撼了!!!!!!!!!

而究竟要怎麼得到這項大獎呢? 很簡單,你只需要憑 $110$ 元以上發票就能到各大服務台索取抽獎卡片,就有機會得到汽車一台!!

但是這下又讓百貨公司的高層頭疼了... 這個活動吸引了近百萬人而來,

如果採用一般的抽獎方式,那光是人力成本跟時間就要花費不少。

因此,他們想到一個好方法,
在每張卡片上面印有一個數字 $P$ ($110 \leq P \leq 1100000$ 且 $P\in\mathbb{N}$),而每個數字 $P$ 都會對應到這張卡片可以得到的分數 $S$,
你的分數將當場被記錄到主電腦中,以準備之後的抽獎活動,

然而,為了再增添話題性跟業績(?),一個人可以多次索取這種抽獎卡 (當然,你必須要有相對應數量張的發票),

雖說是「抽獎」,不過由於這個方法的特性,獎品將是發給總成績 $S_T$ 前 $110$ 名的幸運兒!

--
第 $i$ 張卡片的分數計為 $S_i$ 計算方法如下:

$G_j = \left \{ \begin{array}{rcl} 0 & \mbox{if} & \gcd(P,j) >1 \\ 1 & \mbox{if} & \gcd(P,j)=1 \end{array} \right .$, $ 1 \leq j \leq P $

$ S_i = \sum_{j=1}^ {P}{G_j} $

假設你領了 $n$ 張,總成績 $S_T$ 計算方式則是:

$ S_T = {\frac{1}{n}} \sum_{i=1}^ n{S_i} $
--

Input Format

第一行有一個整數 $T$ ($1 \leq T \leq 110$),代表以下有幾組測試資料。

對於每筆測試資料的首行有一個正整數 $C$ ($1 \leq C \leq 50$) 代表總共拿了幾次卡片

都有一行,包含著一個正整數 $P$ ($110 \leq P \leq 1100000$),代表所持號碼牌上的號碼。

Output Format

對於每筆測試資料,請輸出一行包含一個正實數 $S_T$ ,代表著這張號碼牌所對應到的分數 (四捨五入到小數點下第二位)。

Sample Input

2
3
110
111
112
2
210
245

Sample Output

53.33
108.00

Hints

Problem Source

原TIOJ1536 / Problem Setter: Skyly

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10