projecteuler No.100 Arranged probability

題目連結：

Problem 100 Arranged probability

題目100：要使取到兩個藍碟子的幾率是50%需要有多少個藍碟子？

通過人數：7708

題目分析：

這道題記盤子數為n，藍盤子為p，則相當于要解方程：

n(n-1)=2p(p-1)的第一組使得n>10^12的正整數解的p值。

對于這個方程我最開始還是嘗試蠻力解，不過幾分鐘的時間隻從10^12之後搜了1億個數...于是顯然蠻力解法不行...

于是恒等變形成，等價于如下方程：

(2n-1)^2-2(2p-1^2)=-1

這是第二型佩爾方程。

而關于第二型佩爾方程的正整數解的通用解法，好像還是一個未解決問題。

畢竟在谷歌學術中搜尋第II型佩爾方程，會查到不少關于這個問題的子問題或者交集問題的論文。

于是就考慮曲線的求解方法。

一方面，通過一篇博文（Project Euler 100: Finding the number of blue discs for which there is 50% chance of taking two blue.）,得知了這個網站：http://www.alpertron.com.ar/QUAD.HTM，給出了二進制二次不定方程正整數解的線上求解工具。

另一方面，考慮到(1,1)為這個方程的最小解，記為(x1,y1)則第二型佩爾方程有通解公式：

xn=(1/2)((x1+y1sqrt(d))^(2n+1)+(x1-y1sqrt(d))^(2n+1))

yn=(1/(2sqrt(d)))((x1+y1sqrt(d))^(2n+1)-(x1-y1sqrt(d))^(2n+1))

其中，d=2.

于是，構成線性地推：

x_(n+1) = 3x_n+4y_n

y_(n+1) = 2x_n+3y_n

這樣就可以求解了。

解題過程：

利用上面的分析，可以寫出如下代碼：

long long int x[100];
long long int y[100];

x[0] = 1;
y[0] = 1;

for (int i = 1;i <= 16; i++)
{
	x[i] = 3 * x[i-1] + 4 * y[i-1];
	y[i] = 2 * x[i-1] + 3 * y[i-1];

	if (x[i] > (long long int)1000000000000)
	{
		printf("%lld\n",(y[i] + 1) / 2);
		break;
	}
}
return 0;
           

最後列印出結果： 756872327473

以上隻是我做題時的解法。

如果有更好的解法、更好的思路，歡迎評論讨論~O(∩_∩)O~