注意 : このページには、Project Eulerのネタバレが書かれています。自力で解きたい方はブラウザーの「戻る」ボタンを押してください。
Caution : This page contains commentary of Project Euler. If you solve problem by yourself, Please click back button of your webbrowser.
A(n)を100万から始めて、割り切れる数を下からインクリメントして探しました。kは、11%n、余りに11足してまた余りを求めて…で余りが0になるまで繰り返してレピュニットの長さkを求めました。随分遅かったです。
フォーラム見たら、nに対してレピュニット長kをインクリメントして計算していました。そちらの方が計算の空振り少ないので、早くなりました。
ただの二重ループなのですが、radをソートして、c/rad(c)までの総当りで済みますよ、とフォーラムに書かれていたのでやってみたら実際速くなりました。
ループの回数を数えたら随分ループの数が減っていたので、単なる総当りと言っても色々あるなー、と。
青いディスクがBLUE個、赤いディスクがRED個箱に入っていて、2度続けてディスクを取り出した場合、取り出した2つのディスクの両方が青の確率が\(\frac{1}{2}\)の確率は、
ディスク全体の数 ALL = BLUE + REDと置き、
\(\frac{BLUE}{ALL} * \frac{BLUE-1}{ALL-1} = \frac{1}{2}\)
と書ける。ペル方程式に帰着させ、ALLが初めて\(10^{12}\)を超える際のBLUEを求める。
\(\frac{BLUE}{ALL} * \frac{BLUE-1}{ALL-1} = \frac{1}{2}\)
\(\frac{BLUE^2-BLUE}{ALL^2-ALL} = \frac{1}{2}\)
\(2BLUE^2-2BLUE=ALL^2-ALL\)
平方完成させて、
\(\frac{1}{2}(4BLUE^2-4BLUE) = ALL^2-ALL\)
\(\frac{1}{2}(2BLUE-1)^2 - \frac{1}{2} = ALL^2-ALL\)
\(\frac{1}{2}(2BLUE-1)^2 - \frac{1}{2} = \frac{1}{4}(4ALL^2-4ALL)\)
\(\frac{1}{2}(2BLUE-1)^2 - \frac{1}{2} = \frac{1}{4}(2ALL-1)^2 - \frac{1}{4}\)
両辺に4を掛けて、
\(2(2BLUE-1)^2 - 2 = (2ALL-1)^2 - 1\)
\(2(2BLUE-1)^2 - (2ALL-1)^2 = 1\)
両辺にマイナスをかけて、
\(- 2(2BLUE-1)^2 + (2ALL-1)^2 = -1\)
\((2ALL-1)^2 - 2(2BLUE-1)^2 = -1\)
2ALL-1 = X、2BLUE-1=Yと置き、
\(X^2 - 2Y^2 = -1\)の形のペル方程式を得る。ペル方程式の漸化式を求める。
ペル方程式を参考にした。
\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}a & Db \\ b & a\end{pmatrix}\binom{x_n}{y_n}\)
a=Xの最小の値、
b=Yの最小の値、
D=Yの係数
より、
X=2ALL-1なので、最小の値はBLUEが1枚、BLUE=1、REDが0枚、従ってALLが\(2*1-1=1\)。ALL=1の場合。1が最小。
Y=2BLUE-1なので、最小の値はBLUE=1の場合。\(2*1-1 = 1\)。1が最小。
よって、a=1、b=1、D=2。
\(\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix}1 & 2 \\ 1 & 1 \end{pmatrix}\binom{X_n}{Y_n}\)
行列の掛け算は、
\(\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \binom{b_1}{b2}=\begin{pmatrix} a_{11}*b_1 + a_{12}*b_2 \\ a_{21}*b_1 + a_{22}*b_2 \end{pmatrix}\)
なので、
\(\begin{pmatrix} 1 & 2 \\ 1 & 1\end{pmatrix}\binom{X_n}{Y_n}=\begin{pmatrix}X_n + 2Y_n \\ X_n + Y_n\end{pmatrix}\)
従って、
\(X_{n+1}=X_n+2Y_n\)
\(Y_{n+1}=X_n+Y_n\)
の漸化式を得る。
(2ALL-1)=X、(2BLUE-1)=Yと置いたので、
\(ALL=\frac{X+1}{2}\)
\(BLUE=\frac{Y+1}{2}\)
XとYは\(2k-1\)の形で奇数なので、XとYが奇数の場合のみALLとBLUEを計算して、ALLが初めて\(10^{12}\)を超えた時のBLUEを答えとした。計算量は\(O(n)\)。
※ペル方程式の漸化式の公式の証明
ペル方程式を参考にした。
一般に、
\((a + b\sqrt{D})^n = x_n + \sqrt{D}y_n\)
を満たす整数の数列\(x_n,y_n\)が、次の漸化式を満たすと示す。
\( \left\{\begin{align} x_{n+1} &= ax_n + bDy_n\\y_{n+1} &= bx_n + ay_n \end{align}\right. \)
\((a + b\sqrt{D})^{n+1} = (a + b\sqrt{D})^n(a + b\sqrt{D})\)
\((a + b\sqrt{D})^n = x_n + \sqrt{D}y_n\)なので代入して、
\((a + b\sqrt{D})^{n+1}\)
\(=(x_n+\sqrt{D}y_n)(a + b\sqrt{D})\)
\(= ax_n + b\sqrt{D}x_n + a\sqrt{D}y_n + bDy_n\)
\(= (ax_n + bDy_n) + \sqrt{D}(bx_n + ay_n)\)
この式は\(x_{n+1} + \sqrt{D}y_{n+1}\)に等しいので、
\( \left\{\begin{align} x_{n+1} &= ax_n + bDy_n\\y_{n+1} &= bx_n + ay_n \end{align}\right. \)
が示された。