斐波那契数列

 

1．x，y∈[1…k]，且x，y，k∈Z

2.（x^2-xy-y^2）^2=1

给你一个整数k，求一组满足上述条件的x，y并且使得x^2+y^2的值最大。

小FF得到答案后，用石笔将答案书写在羊皮纸上，那么就能到达王室的遗产所在地了。

 

证明可直接转%%%%

化简式子：

$(x^2-xy-y^2)^2=1$

$(y^2+xy-x^2)^2=1$

$((x+y)^2+xy+2*x^2)^2=1$

$((x+y)^2+(x+y)*x+x^2)^2=1$

 

斐波那契数列的性质之一：

${f_n}^2-f_{n-1}*f_{n+1}=-1^{n-1}$

把$f_{n+1}$替换成$f_n+f_{n-1}$

${f_n}^2-f_{n}*f_{n-1}-{f_{n-1}}^2=-1^{n-1}$

然后就发现这两个式子很像

 

我们要求$x^2+y^2$的最大值。

就是求${f[n]}^2+{f[n-1]}^2$的最大值。

#include
     
      #include
      
       #define N 10000#define LL long longusing namespace std;LL f[N],n;int main(){    scanf("%lld",&n);    f[0]=f[1]=1;    for(int i=2;;i++){        f[i]=f[i-1]+f[i-2];        if(f[i]>n){            printf("%lld %lld\n",f[i-1],f[i-2]);            return 0;        }    }        return 0;}