普及C组第二题(8.4)

2266. 古代人的难题 
(File IO): input:puzzle.in output:puzzle.out

时间限制: 1000 ms  空间限制: 60000 KB

题目：

门打开了， 里面果然是个很大的厅堂。但可惜厅堂内除了中央的一张羊皮纸和一根精致的石笔，还有周围几具骷髅外什么也没有。 难道这就是王室的遗产？ 小 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都是整数

CODE:

#include<iostream>
#include<cstdio>
using namespace std;
long long i=0,k;
struct hh
{
    long long num1,num2,sum;
};
hh fb[86];
int main()
{
    cin>>k;
    fb[0].num1=1;
    fb[0].num2=1;
    fb[0].sum=1;
    while(fb[i].sum<k)
    {
        i++;
        fb[i].num1=fb[i-1].num1+fb[i-1].num2;
        fb[i].num2=fb[i-1].num1;
        fb[i].sum=fb[i-1].sum+fb[i].num2;
    }
    cout<<fb[i].num1<<" "<<fb[i].num2;
}

思路：

你看看这数据，这是人能干的吗

(ノ=Д=)ノ┻━┻

考场上就蒙了，一点求生欲都没有，唉。

其实这道题就是暴力打下表就出来，很容易的发现这货居然是斐波那契数列，

长路漫漫，唯表作伴。定义一下结构体，一下子就出来了。

完结撒花！！！

其实数据很小，那个10的18次方是吓唬人的，开到86个数组就能搞。

(ノ=Д=)ノ┻━┻