古代人的难题

(File IO): input:puzzle.in output:puzzle.out

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

Time to Submit: 01:57:40

题目描述

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

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

输入

一个整数 k

输出

输出文件仅一行，两个整数；

两个整数分别表示 x 和 y。x, y 之间用一个空格隔开。

样例输入

1995

样例输出

1597 987

数据范围限制

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

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

提示

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

Solution(P1775&P1936)

悄悄地打个表（其实就是在暴力枚举模拟的过程）

table_code

#include
     
      using namespace std;unsigned long long k;int main(){
        freopen("table.txt","w",stdout);//    cin>>k;    int maxans=1,maxx=1,maxy=1;    for(k=2;k<=10000;k++)    {                for(int x=1;x<=k;x++)    for(int y=1;y<=x;y++)    {        if((x+y)*(x-y)==x*y+1||(x+y)*(x-y)==x*y-1)        if(maxans

table.txt

k x y2 2 13 3 24 3 25 5 36 5 37 5 38 8 59 8 510 8 511 8 512 8 513 13 814 13 815 13 816 13 817 13 818 13 819 13 820 13 821 21 1322 21 1323 21 1324 21 1325 21 1326 21 1327 21 1328 21 1329 21 1330 21 1331 21 1332 21 1333 21 1334 34 2135 34 2136 34 2137 34 2138 34 2139 34 2140 34 2141 34 2142 34 2143 34 2144 34 2145 34 2146 34 2147 34 2148 34 2149 34 2150 34 2151 34 2152 34 2153 34 2154 34 2155 55 3456 55 3457 55 3458 55 3459 55 3460 55 3461 55 3462 55 3463 55 3464 55 3465 55 3466 55 3467 55 3468 55 3469 55 3470 55 3471 55 3472 55 3473 55 3474 55 3475 55 3476 55 3477 55 3478 55 3479 55 3480 55 3481 55 3482 55 3483 55 3484 55 3485 55 3486 55 3487 55 3488 55 3489 89 5590 89 5591 89 5592 89 5593 89 5594 89 5595 89 5596 89 5597 89 5598 89 5599 89 55100 89 55

table.txt

哈，这不是熟悉的斐波那契数列兄弟嘛

那么问题就变成了：

已知k，求x，y。

其中x，y属于斐波那契数列相邻了两项且x>y（P1936 水晶灯火灵中是m<n）

使得k>=x&&k<x+y

//文末有证明！

Code(P1775)

1 #include
     
       2 using namespace std; 3 unsigned long long k; 4 void make() 5 { 6     int i=0; 7     unsigned long long x=1,y=0,t,l=0,r; 8     while(true) 9     {10         t=x;11         x=x+y;12         y=t;13         if(k>=x&&k
      
       >k;26     make();27     return 0;28 }29 /*30 1. x, y sy [1..k], 且x，y，k sy Z；31 2. （x^2 - xy - y^2）^2 = 132 给你一个整数 k， 33 求一组满足上述条件的 x， y 34 并且使得 x^2 + y^2 的值最大。35 36 */

也可以利用打的表（修改了一下）

1 #include
     
       2 using namespace std; 3 unsigned long long k; 4 unsigned long long table[300]={ 5 1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269, 6 2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903, 7 2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879, 8 956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141, 9 117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,10 8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,11 420196140727489673,679891637638612258,1100087778366101931};12 int main()13 {14 //    freopen("puzzle.in","r",stdin);15 //    freopen("puzzle.out","w",stdout);16     cin>>k;17     for(int i=1;i<=300;i++)18         if(k>=table[i]&&k

但是请注意，上面这种方法请在工具 -> 编译选项 -> 代码生成/优化 -> 代码警告中把“忽略所有警告信息” 设为“Yes”

Code(P1936)

1 #include
     
       2 using namespace std; 3 unsigned long long k; 4 void make() 5 { 6     int i=0; 7     unsigned long long x=1,y=0,t,l=0,r; 8     while(x
      
       =x&&k

证明

本文提供两种证明方法。敬请过目~

证明（P1775）

(x^2 - xy - y^2)^2

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

= [(x+y)^2 - xy - 2*x^2]^2

=[(x+y)^2 - (x+y)*x - x^2]^2

由上式可知，如果x, y 满足条件2，那么x+y, y 也满足条件2。

那么Fibomacci 中小于等于k 的最大两个相邻的数即为试题所需的解。

证明（P1936）

记f(n,m)=(n^2-mn-m^2)^2

则有f(m+n,m)=[(m+n)^2-n(m+n)-n^2]^2=(m^2+mn-n^2)^2=(n^2-mn-m^2)^2=f(n,m)

易得f(1,1)=1

故1=f(1,1)=f(2,1)=f(3,2)=...

转载于:https://www.cnblogs.com/send-off-a-friend/p/11298683.html

你可能感兴趣的文章