Luogu P1775 the problem of the ancients _NOI Guide 2010 improve (02) (Fibonacci + Mathematics)

meaning of the title

It is known that X and y are integers, and satisfy the following two conditions:

1．x，y∈[1…k]，And X, y, K Z

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

I’ll give you an integer k, find a set of X and y that satisfy the above conditions, and make the value of x^2+y^2 the largest.

k<=10¹⁸

An explanation

This problem needs to be pushed.

(x²-xy-y²)²=1

(y²+xy-x²)²=1

[(x+y)²-xy-2x²)]²=1

[(x+y)²-(x+y)x-x²)]²=1

Then, because the Fibonacci sequence has one property:

The way to turn f[n+1] into f[n]+f[n-1] becomes:

f[n]²-f[n]f[n-1]-f[n-1]²=(-1)^n-1

It is found that these two formulas are very similar.

After careful observation, we find that when x+y=f[n] and x=f[n-1] are formed

Order x1=x+y; y1=x;

(x1²-x1y1-y1²)²=1That is to say, when x1=f[n], y1=f[n-1] is set up.

We require X.²+y²The maximum value.

It is seeking f[n].²+f[n-1]²The maximum value.

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 unsigned long long n,f[2000000];
 8 int now;
 9 int main(){
10     scanf("%llu",&n);
11     now=2; 
12     f[0]=0;f[1]=1;f[2]=1;
13     while(n>=f[now]){
14         now++;
15         f[now]=f[now-1]+f[now-2];
16     }
17     printf("%llu %llu",f[now-1],f[now-2]);
18     return 0; 
19 }