Problem 100 Arranged probability （丢番图方程）

「爱情、让人受尽委屈。」 2022-07-14 01:58 19阅读 0赞

## Arranged probability ##

### Problem 100 ###

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, P(BB) = (15/21)×(14/20) = 1/2.

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 1012 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

题解：b\*(b-1) / (n\*(n-1)) = 1/2

==> n^2-2b^2-n+2b = 0

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

==>上面的是第二型佩尔方程

==>关于第二型佩尔方程的正整数解的通用解法，好像还是一个未解决问题。

==>考虑到(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

==>  
n0=0,b0=0 and n0=1,b0=1  
n(n+1) = P\*n(n)+Q\*b(n)+K  
b(n+1) = R\*n(n)+S\*b(n)+L  
P=3, Q=2, K=-2, R=4, S=3, L=-3

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
    	ll n=21,b=15;
    	
    	while(n<1000000000000L)
    	{
    		ll tmp_n=4*b+3*n-3;
    		ll tmp_b=3*b+2*n-2;
    		n=tmp_n;
    		b=tmp_b;
    	}
    	cout<<b<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关 DP训练之：100个动规方程（转载）

DP训练之：100个动规方程（转载）最近这一周主要就是练习DP了，感觉DP不多做点题，完全找不到一些题目的状态转移方程当然100个动规方程肯定是要了解的直接给个

向右看齐/ 2023年06月30日 02:37/ 0 赞/ 5 阅读

相关 Double乘100会丢精度解决

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tse

系统管理员/ 2023年06月21日 12:21/ 0 赞/ 112 阅读

相关 zoj3777 Problem Arrangement(状态压缩dp)

题目链接：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777][http_acm.zju.ed

ゝ一世哀愁。/ 2022年08月26日 15:21/ 0 赞/ 217 阅读

相关 HDU 5719 Arrange

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5719][http_acm.hdu.edu.cn_showproblem.ph

待我称王封你为后i/ 2022年07月20日 12:14/ 0 赞/ 156 阅读

相关 Problem 100 Arranged probability （丢番图方程）

Arranged probability Problem 100 If a box contains twenty-one coloured discs, comp

「爱情、让人受尽委屈。」/ 2022年07月14日 01:58/ 0 赞/ 20 阅读

相关 441_ Arranging_Coins

/ 441. Arranging Coins You have a total of n coins that you want to for

旧城等待，/ 2022年06月08日 00:51/ 0 赞/ 168 阅读

相关经典算法详解（7）丢番图的墓志铭

丢番图的一生1/6是童年，青少年时代占了他一生的1/12，随后1/7他说过着独身的生活，结婚后5年他生了一个儿子，他感到很幸福，可是这孩子的生命只有他父亲的一半，儿子去世后，丢

àì夳堔傛蜴生んèń/ 2022年04月25日 00:08/ 0 赞/ 436 阅读

相关 npm install出现This is probably not a problem with npm错误

使用npm install 安装npm时出现[This is probably not a problem with npm. There is likely addition

柔情只为你懂/ 2022年01月22日 00:37/ 0 赞/ 997 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 322 阅读

相关 Josephus problem（约瑟夫问题，丢手绢问题）

约瑟夫问题 -------------------- 约瑟夫环问题是一个数学应用题：已知n个人（以编号1，2，3.....，n)围坐在一张圆桌的周围。从编号为k

蔚落/ 2021年11月26日 12:26/ 0 赞/ 358 阅读