HDU 多校1.5

Expectation Division

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0
Special Judge

Problem Description

To be frank with you, this problem is a classic problem of tremendous magnitude which may increase the difficulty of this problem.

We define a type of operation concerning a positive integer n (n>1) as to replace it with an integer d , one of factors of n (1≤d≤n) .

You are given a positive integer n and then we will ask you to determine the expectation number of times to utilize this type of operation if we want to change n into 1 by operating again and again, assuming each possible d in each operation has equal possibility to select.

For the sake of calculation, n and all its distinct prime factors p1,p2,⋯,pm will be given, satisfying n has m distinct prime factors exactly.

 

Input

The input contains multiple test cases.

For each test case:

The first line contains two positive integers n and m which indicates m is the number of distinct prime factors of n , satisfying 2≤n≤1024 .

The second lines contains m distinct prime numbers p1,p2,⋯,pm , satisfying 2≤pi≤106 .

About 2⋅105 test cases in total.

Warm Tips for C/C++: __int128_t is available here but standard solutions of this problem do not use this compiler-dependent data type.

 

Output

For each test case, output "Case #x : y " in one line (without quotes), where x indicates the case number starting from 1 and y denotes the expectation number of times to utilize this type of operation of corresponding case. Your answer will be considered correct if its absolute or relative error won't exceed 10−9 .

 

Sample Input

2 1 2 4 1 2 6 2 2 3 8 1 2 10 2 2 5 12 2 2 3

 

Sample Output

Case #1: 2.0000000000 Case #2: 2.5000000000 Case #3: 2.6666666667 Case #4: 2.8333333333 Case #5: 2.6666666667 Case #6: 3.0333333333