問題一覧 > 通常問題

No.248 ミラー君の宿題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-8}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 8
作問者 : Min_25Min_25
3 ProblemId : 580 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:12

問題文

ミラー君は,ある $N$ 個の互いに異なる奇素数 $p_1, p_2, ..., p_N$ によって計算された 2 つの積,
$$
P = \prod _{i=1}^N p_i,\ \ Q = \prod _{i=1}^N (p_i - 1)
$$
を受け取った時に,手計算で $P$ を素因数分解する宿題をしなくてはいけません.

ミラー君は,調子の良いときには,ある数が素数であるかどうかについては一瞬で正しく判断することができるのですが,素因数分解は得意ではありません.

あなたはミラー君の手助けをするため,以下のような乱択アルゴリズムを教えることにしました.

乱択アルゴリズム: $F(P, Q)$

  • 入力: 正の整数 $P, Q$
  • 出力: $P$ の素因数の集合
  1. $P$ が 1 であれば,空集合 $\emptyset$ を返す.
  2. $P$ が素数であれば,$\{P\}$ を返す.
  3. それ以外の場合は,$0 < r \le P$ なる正の整数 $r$ を一様ランダムに選択し,$g = \mathrm{gcd}(r, P)$ を計算して,
    1. $g = P$ であったならば,$F(P, Q)$ を返す.
    2. $1 < g < P$ であったならば,$F(g, Q) \cup F(P/g, Q)$ を返す.
    3. $g = 1$ であったならば,$Q$ を奇数 $q$ と非負整数 $e$ を用いて,$Q = 2^e \times q$ と書き直し,$c = r^{q} \pmod{P}$ を計算する.次に,$c^2 \ne 1 \pmod{P}$ である限り,$c \leftarrow c^2 \pmod{P}$ と更新し続ける.その後,
      1. $1 < c < P - 1$ であったならば,$h = \mathrm{gcd}(c - 1, P)$ として,$F(h, Q) \cup F(P / h, Q)$ を返す.
      2. $c = 1$ または $c = P - 1$ であったならば,$F(P, Q)$ を返す.

乱択アルゴリズムを教えてもらったミラー君ですが,$F(P, Q)$ の計算によって $P$ の素因数分解を得ようとしたときに,関数 $F$ が再帰的に何回呼び出されるのか予想できず,その不安から未だに宿題に手を付けることができていません.

そこであなたはミラー君を安心させるために,$F(P, Q)$ の計算が停止するまでに関数 $F$ が呼び出される回数の期待値 $E$ を教えることにしました.

入力

$T$
$N_1$
$P_{1,1}\ P_{1,2}\ ...\ P_{1,{N_1}}$
$N_2$
...

$1$ 行目に例題の個数 $T$ が与えられ,その後 $2T$ 行に例題が与えられる.
各例題は $1$ 行目に素因数 $p_i$ の個数 $N$ が与えられ,$2$ 行目に互いに異なる奇素数 $p_1, ..., p_N$ が与えられる.
ここで,ミラー君に与えられる $P, Q$ は問題文の通りに計算されているものとする.

制約条件:

  • 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$ ($N$ は互いに異なる)
    • $3 \le p_i < 2^{63}$
ジャッジ解の最悪実行時間は C++ で 0.3 秒ほどです.

出力

$E_1$
$E_2$
...
各例題に対し,最初に $F(P, Q)$ を実行をしてから停止するまでに関数 $F$ が呼び出される回数の期待値 $E$ を計算し,その値が有限値である場合にはその値を小数点以下 9 桁まで出力し,そうでない場合には文字列 "oo" を出力せよ.

$E$ が有限値であった場合の誤差は,$10^{-8}$ まで許容される.

なお,ミラー君の素数判定は 100% 正しいと仮定してよい.

サンプル

サンプル1
入力
4
1
3
2
3 5
3
3 5 7
13
3 5 7 11 13 17 19 23 29 31 37 41 43
出力
1.000000000
3.250000000
5.438775510
27.210442972

1 つ目の例題では,$P$ が素数であるため,$F$ は常に 1 回しか実行されない.
2 つ目の例題では,$P = 3 \times 5$ は合成数であり,$Q = 2 \times 4 = 2^3 \times 1$ である.$r$ として,

  • $3, 5, 6, 9, 10, 12$ を引いた場合には,$P = 3 \times 5$ と分解できる.
  • $2, 4, 7, 8, 11, 13$ を引いた場合には,$c$ は順に $4, 4, 4, 4, 11, 4$ まで更新され,いずれも,$P = 3 \times 5$ と分解できる.
  • $1, 14, 15$ を引いた場合には,$P$ の分解を行うことができず,$F$ を再び呼び出すことになる.
つまり,$F$ が呼び出される回数の期待値 $E$ は,$E = 1 + \frac{3}{15} E + \frac{12}{15} \times (1 + 1)$ と表すことができ,$E = \frac{13}{4}$ となる.

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