题目100：要使取到两个蓝碟子的几率是50%需要有多少个蓝碟子？

欧拉计划

Arranged probability

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, .

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over discs in total, determine the number of blue discs that the box would contain.

题目：

如果一个盒子里有 21 个有色的碟子，15 个蓝色的和 6 个红色的。从中随机取两个，可知取到两个蓝碟子的几率是 。

下一个满足此条件（即随机取两个碟子的情况下取到两个蓝色碟子的几率是 50%）的情况是 85 个蓝碟子和 35 个红碟子。

对于包含超过 个碟子的情况中，满足上述条件的并包含最少碟子的情况，该情况下共需要多少个蓝碟子？

$DIM

版主厉害，占据所有头条

k329266978

弱弱地问一句，如何定义一个long更大的数据？？？百度说的long long好像不被接受。
不然那个10^12怎么描述？？？

小甲鱼

k329266978 发表于 2016-8-12 14:22
弱弱地问一句，如何定义一个long更大的数据？？？百度说的long long好像不被接受。
不然那个10^12怎么描述 ...

百度都差不多是过时的代名词了，C99：

jerryxjr1220

因为10**12的数字量太大了，暴力破解肯定行不通。这样就要从其他方面着手。
然后我发现了很有趣的解法“找规律”：
首先根据题设，写函数，找出前几个符合条件的解：

1. import math
   
2. def func(t):
   
3.         tb = (1+math.sqrt(2*t*t-2*t+1))
   
4.         if tb % 2 == 0:
   
5.                 return int(float(tb)/2)
   
6.         else:
   
7.                 return False
   
8. 
   
9. print "(blue,red,total)"
   
10. t = 3
    
11. b = func(t)
    
12. while t < 100000:
    
13.         while b == False:
    
14.                 t+=1
    
15.                 b = func(t)
    
16.         print (b,t-b,t)
    
17.         t+=1
    
18.         b = func(t)

复制代码

得到结果：

1. (blue,red,total)
   
2. (3, 1, 4)
   
3. (15, 6, 21)
   
4. (85, 35, 120)
   
5. (493, 204, 697)
   
6. (2871, 1189, 4060)
   
7. (16731, 6930, 23661)
   
8. (97513, 40391, 137904)
   
9. [Finished in 0.2s]

复制代码

通过观察前几项，可以发现：
1. 红盘子red符合递归：red（n）=6*red（n-1）-red（n-2） 【red（0）=0，red（1）=1】
2. 总盘子total符合递归：total（n）=6*total（n-1）-total（n-2）-2 【total（0）=1，total（1）=4】
有了这2个递推关系，就可以写递推关系式了。

1. def digui(t):
   
2.         red = [0,1]
   
3.         total = [1,4]
   
4.         while total[-1] < t:
   
5.                 red.append(6*red[-1]-red[-2])
   
6.                 total.append(6*total[-1]-total[-2]-2)
   
7.         print "blue: " + str(total[-1]-red[-1])
   
8. 
   
9. digui(10**12)

复制代码

结果：

1. blue: 756872327473
   
2. [Finished in 0.1s]

复制代码

轻松搞定

jerryxjr1220

顺利解决欧拉计划前100题，自己庆贺一下！！！

永恒的蓝色梦想

本质上是解二元二次不定方程

guosl

本题是求方程a(a-1)/((a+b)(a+b-1)=1/2的a+b>=1000000000000的最小整数解。
整理方程得a^2-(2b+1)a-(b^2-b)=0，
根据二次方程的求根公式得：
a=(y+x+1)/2，其中y=2b,x^2=2y^2+1，由于a,b都是整数故x,y也都是整数，从而x,y满足
Pell方程x^2 - 2 y^2 = 1，这个方程的最小正整数解是x(1)=3,y(1)=2
这个方程的一般递推解如下：（具体参照数论中的Pell方程的通解）
x(n)=x(1)*x(n-1)+2*y(1)*y(n-1)
y(n)=y(1)*x(n-1)+x(1)*y(n-1)
我们可以逐步求出x(n)和y(n)进而获得a和b。

1. /*
   
2. 答案：756872327473
   
3. */
   
4. #include <iostream>
   
5. using namespace std;
   
6. 
   
7. const long long N = 1000000000000LL;
   
8. 
   
9. int main(void)
   
10. {
    
11.   long long x1 = 3, x2, y1 = 2, y2;
    
12.   while (true)
    
13.   {
    
14.     x2 = 3 * x1 + 4 * y1;
    
15.     y2 = 2 * x1 + 3 * y1;
    
16.     long long b = y2 / 2;
    
17.     long long a = y2 + x2 + 1;
    
18.     a = a / 2;
    
19.     if (a + b >= N)
    
20.     {
    
21.       cout << a << endl;
    
22.       break;
    
23.     }
    
24.     x1 = x2;
    
25.     y1 = y2;
    
26.   }
    
27.   return 0;
    
28. }

复制代码