vijos1543(极值问题)解题报告

(n^2-m*n-m^2)^2=1

是齐次多项式，设n>=m,n=m+t(t>=0)。

n^2-m*n-m^2=t^2-m*t-m^2

所以(t^2-m*t-m^2)^2=1。

如果n,m(n>=m)是满足条件的一对数，则(m,n-m)（原较小数，原较大数-原较小数）也是满足条件的一对数。依次类推，因为两个数越变越小（n> n-m），且不会小于0（m>0，n-m>0），所以最终有一个数为0。

假设当m=0， (n^2)^2=1,n=1。

根据倒推，0,1,1,2,3,5,8,…… 为斐波那契数列。

 

Attention：

1.开的数组大小

2.开长整形

#include <stdio.h>
#include <stdlib.h>

int main()
{
    long k,i;
    long long f[100];
    scanf("%ld",&k);
    f[0]=0;
    f[1]=1;
    i=1;
    while (f[i]+f[i-1]<=k)
    {
        i++;
        f[i]=f[i-1]+f[i-2];
    }
    printf("%lld
",(long long)(f[i]*f[i]+f[i-1]*f[i-1]));
    return 0;
}