ACM-ICPC-OJ训练营

问题 1790 --Expectation Division

1790: Expectation Division

时间限制: 4 Sec 内存限制: 128 MB
提交: 2 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

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>1) as to replace it with an integer

d, one of factors of

(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

1by 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.

输入描述

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.

输出描述

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.

样例输入

样例输出

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

来源

[提交][状态]