当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6037:Expectation Division

Special Judge 特殊评判
题目描述
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 \leq d \leq 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 $p_1, p_2, \cdots, p_m$ 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 \leq n \leq 10^{24}$.

The second lines contains $m$ distinct prime numbers $p_1, p_2, \cdots, p_m$, satisfying $2 \leq p_i \leq 10^6$.

About $2 \cdot 10^5$ 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}$.
输入样例
2 1
2
4 1
2
6 2
2 3
8 1
2
10 2
2 5
12 2
2 3
输出样例
Case #1: 2.0000000000
Case #2: 2.5000000000
Case #3: 2.6666666667
Case #4: 2.8333333333
Case #5: 2.6666666667
Case #6: 3.0333333333
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6037

最后修改于 2020-10-25T23:27:45+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 131072/131072K(Java/Others)