首页 > 代码库 > 51nod 1537分解

51nod 1537分解

题目传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1537

神犇题解传送门:http://blog.csdn.net/qingshui23/article/details/52350523

证明好巧妙,给跪OTZ

题目的式子:$ {\left( {1{\rm{ + }}\sqrt 2 } \right)^{\rm{n}}} $,设其乘开之后为 $ {\rm{a + b}}\sqrt 2 $

考虑相对的式子:$ {\left( {1{\rm{ - }}\sqrt 2 } \right)^{\rm{n}}} $,则乘开后为 $ {\rm{a + b}}\sqrt 2  $

两式相乘,得到 $ {( - 1)^n} = {a^2} - 2{b^2} $

分奇偶讨论,如果n为偶数,则当 $ m = {a^2} $, $ m - 1 = {a^2} - 1 = 2{b^2} $,$ \sqrt m  + \sqrt {m - 1}  = a + b\sqrt 2 $

n为奇数时同理,当 $ m = {a^2} + 1 = 2{b^2} $, $ m - 1 = {a^2} $,$ \sqrt m  + \sqrt {m - 1}  = a + b\sqrt 2 $

所以,不存在无解状况。现在问题是怎么求a。如果打表找规律可以知道,n>=2时,a[n]=2*a[n-1]+a[n-2],初始值为a[1]=a[2]=1;

怎么证明呢?网上没看到有证明,所以自己胡扯一下吧。考虑我们已经有了 $ {\left( {1{\rm{ + }}\sqrt 2 } \right)^{n - 2}} = {a_1} + {b_1}\sqrt 2  $

那么 $ {\left( {1{\rm{ + }}\sqrt 2 } \right)^{n - 1}} = \left( {{a_1} + {b_1}\sqrt 2 } \right)\left( {1 + \sqrt 2 } \right) = {a_2} + {b_2}\sqrt 2  $

即 $ {a_2} = {a_1} + 2{b_1},{b_2} = {a_1} + {b_1} $

同理,可以推出 $ {a_3} = {a_2} + 2{b_2} $

带入a1,a2,可以得到 $ {a_3} = 3{a_1} + 4{b_1} = 2{a_1} + {a_2} $

所以满足上面的递推式。

然后矩阵快速幂搞一发就过啦!

51nod 1537分解