CF1114E 的正确性证明

· · 题解

似乎并没有人证明随机算法的概率（只是引用了官方题解），所以闲着就算一下。

所求概率即为

\frac{1}{n^{30}}\sum_{i_1\dots i_{30}\in\{0,n-1\}}[(i_1,\dots,i_{30})=1]

考虑枚举最大公约数，根据莫比乌斯反演，这就是

\frac{1}{n^{30}}\sum_d\mu(d)\left\lceil\frac{n}{d}\right\rceil^{30}

这样我们可以在 O(n) 的时间内把这个东西算出来。不过我们想要一个纯数学的东西，对上面这个做一个比较准确的估算。

我们考虑计算上式当 n\to \infty 的极限，这就是

\sum_d\mu(d)\frac{1}{d^{30}}=\sum_{d=p_1\dots p_k}(-1)^k\frac{1}{(p_1\dots p_k)^{30}}=\prod_p\left(1-\frac{1}{p^{30}}\right)

熟知上式即为 \dfrac{1}{\zeta(30)}，再根据 \zeta 的通项，\zeta(2n)=\dfrac{(2\pi)^{2n}B_{2n}}{2(2n)!}

查表得 B_{30}=\dfrac{8615841276005}{14322}，代入计算得 \zeta(30)=\dfrac{6892673020804\pi^{30}}{5660878804669082674070015625}

因此正确概率的极限即为

p=\dfrac{5660878804669082674070015625}{6892673020804\pi^{30}}

错误概率约 9.3132\times 10^{-10}.

事实上我们有一种枚举方式的优化：令每次查询的数互不相同，这样得到的新概率是

\frac{1}{n^{\underline{30}}}\sum_d\mu(d)\left\lceil\frac{n}{d}\right\rceil^{\underline{30}}

但是仔细想一想，会意识到这件事情极限上并没有优化：考虑将 \left[\dfrac{n}{d}\right]^{\underline{30}} 展开，注意到除了首项以外其余极限皆为 0，故当 n\to \infty 时极限不变。

以上。