Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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.

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:

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++:

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}$.

提交代码