No.248 Miller's Homework
タグ : / 解いたユーザー数 8
作問者 :
Min_25
Problem Statement
Miller has homework: given the 2 products computed from some $N$ pairwise distinct odd primes $p_1, p_2, ..., p_N$,
$$
P = \prod _{i=1}^N p_i,\ \ Q = \prod _{i=1}^N (p_i - 1)
$$
he must factorize $P$ into primes by hand.
When he is in good form, Miller can correctly determine in an instant whether a given number is prime, but he is not good at prime factorization.
To help Miller, you have decided to teach him the following randomized algorithm.
Randomized algorithm: $F(P, Q)$
- Input: positive integers $P, Q$
- Output: the set of prime factors of $P$
- If $P$ is 1, return the empty set $\emptyset$.
- If $P$ is prime, return $\{P\}$.
- Otherwise, choose a positive integer $r$ with $0 < r \le P$ uniformly at random, compute $g = \mathrm{gcd}(r, P)$, and then:
- If $g = P$, return $F(P, Q)$.
- If $1 < g < P$, return $F(g, Q) \cup F(P/g, Q)$.
- If $g = 1$, rewrite $Q$ using an odd number $q$ and a non-negative integer $e$ as $Q = 2^e \times q$, and compute $c = r^{q} \pmod{P}$. Next, as long as $c^2 \ne 1 \pmod{P}$, keep updating $c \leftarrow c^2 \pmod{P}$. After that:
- If $1 < c < P - 1$, let $h = \mathrm{gcd}(c - 1, P)$ and return $F(h, Q) \cup F(P / h, Q)$.
- If $c = 1$ or $c = P - 1$, return $F(P, Q)$.
Although Miller has been taught the randomized algorithm, he cannot predict how many times the function $F$ will be called recursively when he tries to obtain the prime factorization of $P$ by computing $F(P, Q)$, and this worry has kept him from starting his homework.
So, to reassure Miller, you have decided to tell him the expected value $E$ of the number of times the function $F$ is called until the computation of $F(P, Q)$ halts.
Input
$T$
$N_1$
$P_{1,1}\ P_{1,2}\ ...\ P_{1,{N_1}}$
$N_2$
...
Line $1$ contains the number of test cases $T$, and the test cases are given on the following $2T$ lines.
For each test case, line $1$ contains the number $N$ of prime factors $p_i$, and line $2$ contains the pairwise distinct odd primes $p_1, ..., p_N$.
Here, $P, Q$ given to Miller are assumed to be computed as described in the problem statement.
Constraints:
- Input 1-x
- $1 \le T \le 1000$
- $1 \le N \le 5$
- $3 \le p_i < 2^{21}$
- Input 2-x
- $1 \le T \le 32$
- $1 \le N \le 10$
- $3 \le p_i < 2^{42}$
- Input 3-x
- $1 \le T \le 13$
- $1 \le N \le 13$ (the values of $N$ are pairwise distinct)
- $3 \le p_i < 2^{63}$
Output
$E_1$ $E_2$ ...For each test case, compute the expected value $E$ of the number of times the function $F$ is called from the first execution of $F(P, Q)$ until it halts. If this value is finite, output it to 9 digits after the decimal point; otherwise, output the string "oo".
When $E$ is finite, an error of up to $10^{-8}$ is allowed.
You may assume that Miller's primality testing is 100% correct.
Sample
Sample 1
Input
4 1 3 2 3 5 3 3 5 7 13 3 5 7 11 13 17 19 23 29 31 37 41 43
Output
1.000000000 3.250000000 5.438775510 27.210442972
In the 1st test case, $P$ is prime, so $F$ is always executed only 1 time.
In the 2nd test case, $P = 3 \times 5$ is composite, and $Q = 2 \times 4 = 2^3 \times 1$. As for $r$:
- If one of $3, 5, 6, 9, 10, 12$ is drawn, the factorization $P = 3 \times 5$ is obtained.
- If one of $2, 4, 7, 8, 11, 13$ is drawn, $c$ is updated up to $4, 4, 4, 4, 11, 4$ respectively, and in every case the factorization $P = 3 \times 5$ is obtained.
- If one of $1, 14, 15$ is drawn, $P$ cannot be factorized, and $F$ is called again.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。