問題一覧 > 通常問題

No.248 Miller's Homework

レベル : / AI推定難易度 : 2750 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-8}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : Min_25
お気に入りにしたユーザー ProblemId : 580 / 自分の提出
問題文最終更新日: 2026-10-12 04:33:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 115 (順位表) の他の問題:

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$
  1. If $P$ is 1, return the empty set $\emptyset$.
  2. If $P$ is prime, return $\{P\}$.
  3. Otherwise, choose a positive integer $r$ with $0 < r \le P$ uniformly at random, compute $g = \mathrm{gcd}(r, P)$, and then:
    1. If $g = P$, return $F(P, Q)$.
    2. If $1 < g < P$, return $F(g, Q) \cup F(P/g, Q)$.
    3. 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:
      1. If $1 < c < P - 1$, let $h = \mathrm{gcd}(c - 1, P)$ and return $F(h, Q) \cup F(P / h, Q)$.
      2. 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}$
The worst-case running time of the judge solution is about 0.3 seconds in C++.

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.
Thus, the expected value $E$ of the number of times $F$ is called can be expressed as $E = 1 + \frac{3}{15} E + \frac{12}{15} \times (1 + 1)$, which gives $E = \frac{13}{4}$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。