Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
还是找了一段时间规律的。。。首先挫败状态的线性规律很好找。。但是并没有什么用... 然后就发现了几组比较刺眼的数据 (1,2)(3,5)(8,13)(21,34)。。。 但是其他的数据呢! 之后多列了几组,又发现比如(4,7)(11,18)(29,47)。。。 (6,10)(16,26)。。。 等等,即构成抢义F数列的,如果可以这样递归的话就是log级的时间了,但是关键是不知道何时终止递归,因为第一个不好找啊,比如(4,7)前面的(1,3)就不是。。。 找了半天终于找到了,发现a和b两个数的比都很接近\frac{1+\sqrt{5}}{2},再把这些数研究一下发现它们中间不满足的都是b比较接近\frac{1+\sqrt{5}}{2}*a的下整,因为这题和根号5有千丝万缕的联系,我大胆假设这个界就是\frac{3-\sqrt{5}}{2}(0.386),没想到就过了! 比如(7,12)就不是,因为\frac{1+\sqrt{5}}{2}*7=11.326<11+\frac{3-\sqrt{5}}{2} 比如(12,20)就是,因为\frac{1+\sqrt{5}}{2}*12=19.416>19+\frac{3-\sqrt{5}}{2} 实际上正确的规律应该是下面这样的吧: (a,b)其中a<b,除了(0,0)之外应该满足: (1)b=\frac{1+\sqrt{5}}{2}*a取上整; (2)\frac{1+\sqrt{5}}{2}*a-(b-1)需要大于\frac{3-\sqrt{5}}{2}. 反正我代码就这么写的。。。过了,但是我纯凭直觉瞎猜的,证不出来,求大神! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator