纪中第四天（c组）（3）

题目

门打开了， 里面果然是个很大的厅堂。但可惜厅堂内除了*的一张羊皮纸和一根精致的石笔，还有周围几具骷髅外什么也没有。 难道这就是王室的遗产？ 小 FF 不信，他仔细阅读了羊皮纸上的内容后发现，里面书写的古代人一直没能解出的难题， 解除这道题目的人只要将答案用石笔写到这张羊皮纸上就能到达王室的宝藏室了。而当小 FF 拿起石笔后，刚刚打开的巨石门突然关上了。 这时小 FF 意识到原来那几具骷髅是在他之前到这里的冒险者，恐怕是因为没能破解这道题而困死在这里了。 小 FF 越想越害怕， 急忙联系到了你，为了能保命，他甚至愿意和你五五分……看来你不得不再次帮他了。 羊皮纸上的问题如下：
      已知 x， y 为整数，且满足以下两个条件：
      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 得到答案后， 用石笔将答案书写在羊皮纸上，那么就能到达王室的遗产所在地了。

输入

一个整数 k

输出

输出文件仅一行，两个整数；
两个整数分别表示 x 和 y。x, y 之间用一个空格隔开。

样例输入

1995

样例输出

1597 987

数据范围限制

对于 30%的数据： 2<=k<=10^4.
对于 100%的数据： 2<=k<=10^18.

提示

Z是数学里面整数集合符号，  即x y k都是整数

思路

这题的公式推倒我不会，但根据打表发现的规律，答案呈斐波那契数列。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
long long k,i;
struct h
{
    long long num1;
    long long num2;
    long long num;
};
h fb[90];
int main()
{
    fb[0].num1=1;
    fb[0].num2=1;
    fb[0].num=1;
    cin>>k;
    while(fb[i].num<k)
    {
        i++;
        fb[i].num1=fb[i-1].num2;
        fb[i].num2=fb[i-1].num1+fb[i-1].num2;
        fb[i].num=fb[i-1].num+fb[i].num1;
    }
    cout<<fb[i].num1<<" "<<fb[i].num2<<endl;
    return 0;
}