Project Euler 100 - Arranged probability

设蓝色碟片和红色碟片的数量分别为$n,m$,简单化简之后即求一个丢番图方程的满足$n+m>10^{12}$的解。

设蓝色碟片和红色碟片的数量分别为$n,m$,得

$$\dfrac{n}{n+m} \times \dfrac{n-1}{n+m-1} = \dfrac{1}{2}$$

即求
$$
\begin{align}
& 2n(n-1) = (n+m)(n+m-1) \
\Rightarrow & n^2 - m^2 + 2nm - n - m = 0 \
\Rightarrow & n^2 + (2m-1)n - m^2 - m = 0
\end{align}
$$
的满足$n+m>10^{12}$的解

考虑$n$为变量,对应的
$$
\begin{align}
\triangle&=(2m-1)^2 + 4(m^2 + m) \
&=8m^2 + 1
\end{align}
$$
对应的解为
$$
n = \dfrac{2m+1 \pm \sqrt{8m^2 + 1}}{2}
$$

因为要求整数解,那么$\triangle$必须是一个平方数, 如果设$\triangle=t^2$, $\triangle$对应的恰为一个佩尔方程:
$$
t^2-8m^2=1
$$
显然其有一组解$t=3, n=1$且为最小解

关于佩尔方程$x^2-Dy^2=1$的一个定理:如果$(x_1, y_1)$是佩尔方程的最小解,则每个解都可以取幂得到,即:
$$
\begin{align}
& x_k+\sqrt{D}y_k=(x_1+\sqrt{D}y_1)^k(k\in N_+) \
\Rightarrow & x_{k+1}+\sqrt{D}y_{k+1}=(x_k+\sqrt{D}y_k)(x_1+\sqrt{D}y_1) (k\in N_+) \
\Rightarrow & x_{k+1}+\sqrt{D}y_{k+1}=(x_1x_k+Dy_1y_k)+(y_1x_k+x_1y_k)\sqrt{D}
\end{align}
$$

对于PE100这道题其实到这里就结束了,虽然要求的是高于$10^{12}$次方的解,但是上述递推式的增长速度是非常快的,只需要暴力递推,枚举$t$和$n$的值并暴力检验即可。

补充内容:

$Trivially$,若要求解第$k$个解时,可以构造矩阵并利用矩阵快速幂来计算。

另外一个需要注意的是关于最小解的求解办法


文章作者: crazyX
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 crazyX !
评论
 上一篇
cf #474 F.Pathwalks - 整体二分 cf #474 F.Pathwalks - 整体二分
给定$10^5$条边,需要找一条路径,使得路径上的边的权值严格递增,并且边的编号也是严格递增的,求最长路径包含的边的数量。 链接Pathwalks 题解似乎正解是DP,不过赛时没想这么多,因为这题有很显然的两维偏序关系,一个即输入的边的
2018-04-08
下一篇 
引以为戒 引以为戒
记录一件小事(或许也说不上小),2018年1月7日晚,和朋友叙旧约饭,开了红星二锅头助兴,没控制住还开了第二瓶,朋友聊着聊着直接趴桌上不省人事……然而这时候我也迷糊了……趁着最后一点意识微信联系了另一个朋友……欠下了巨大的人情……给朋友带来
2018-01-23
  目录