yukicoder-248

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/248 No.248 ミラー君の宿題] ==

=== Description ===

{{{
#!html
<p>给出$N$个互不相同的奇质数$p_1,p_2,\dots,p_N$，定义$P=\prod\limits_{i=1}^{N}p_i, Q=\prod\limits_{i=1}^{N}(p_i-1)$。</p>

<p>考虑如下的随机化算法分解$P$</p>

<div class='input'>
随机化算法：$F(P, Q)$
<ul>
  <li>输入：正整数$P,Q$</li>
  <li>输出：$P$的质因数几个</li>
  <ol>
    <li>如果$P=1$，返回$\emptyset$</li>
    <li>如果$P$是质数，返回$\{P\}$</li>
    <li>其他情况下，在$[1, P]$内随机选择一个整数$r$，令$g=\gcd(r,P)$</li>
    <ol>
      <li>$g=P$，返回$F(P,Q)$</li>
      <li>$1 < g < P$，返回$F(g,Q) \cup F(P/g,Q)$</li>
      <li>$g=1$，令$Q=2^e \times q$（$q$是奇数），计算$c=r^q \pmod P$。然后，一直把$c$更新为$c^2 \pmod P$直到$c^2 \equiv 1 \pmod P$。接下来，</li>
      <ol>
        <li>如果$1 < c < P-1$，令$h=\gcd(c-1,P)$，返回$F(h,Q) \cup F(P/h,Q)$</li>
        <li>如果$c=1$或者$c=P-1$，返回$F(P,Q)$。</li>
      </ol>
    </ol>
  </ol>
</ul>
</div>

<p>求上述随机化算法计算结束的时候，$F$调用次数的期望值$E$。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$T$<br>
$N_1$<br>
$P_{1,1}$ $P_{1,2}$ $\dots$ $P_{1,N_1}$<br>
$N_2$<br>
$\dots$
</p>
<p>
<ul>
<li>Input 1-x：$1 \le T \le 1000, 1 \le N \le 5, 3 \le p_i < 2^{31}$</li>
<li>Input 2-x：$1 \le T \le 32, 1 \le N \le 10, 3 \le p_i < 2^{42}$</li>
<li>Input 3-x：$1 \le T \le 13, 1 \le N \le 13, 3 \le p_i < 2^{63}$</li>
</ul>
</p>
}}}

=== Output ===

{{{
#!html
<p>每组数据输出期望调用次数$E$，误差在$10^{-8}$以内就算对。如果会调用无穷次，输出"oo"。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
4
1
3
2
3 5
3
3 5 7
13
3 5 7 11 13 17 19 23 29 31 37 41 43
</pre>
}}}
输出
{{{
#!html
<pre>
1.000000000
3.250000000
5.438775510
27.210442972
</pre>
}}}

No.248 ミラー君の宿題

Description

给出$N$个互不相同的奇质数$p_1,p_2,\dots,p_N$，定义$P=\prod\limits_{i=1}^{N}p_i, Q=\prod\limits_{i=1}^{N}(p_i-1)$。

考虑如下的随机化算法分解$P$

随机化算法：$F(P, Q)$

输入：正整数$P,Q$
输出：$P$的质因数几个

如果$P=1$，返回$\emptyset$
如果$P$是质数，返回$\{P\}$
其他情况下，在$[1, P]$内随机选择一个整数$r$，令$g=\gcd(r,P)$

$g=P$，返回$F(P,Q)$
$1 < g < P$，返回$F(g,Q) \cup F(P/g,Q)$
$g=1$，令$Q=2^e \times q$（$q$是奇数），计算$c=r^q \pmod P$。然后，一直把$c$更新为$c^2 \pmod P$直到$c^2 \equiv 1 \pmod P$。接下来，

如果$1 < c < P-1$，令$h=\gcd(c-1,P)$，返回$F(h,Q) \cup F(P/h,Q)$
如果$c=1$或者$c=P-1$，返回$F(P,Q)$。

求上述随机化算法计算结束的时候，$F$调用次数的期望值$E$。

Input

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

Input 1-x：$1 \le T \le 1000, 1 \le N \le 5, 3 \le p_i < 2^{31}$
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, 3 \le p_i < 2^{63}$

Output

每组数据输出期望调用次数$E$，误差在$10^{-8}$以内就算对。如果会调用无穷次，输出"oo"。

Sample

Sample 1

输入

41323 533 5 7133 5 7 11 13 17 19 23 29 31 37 41 43

输出

1.0000000003.2500000005.43877551027.210442972