问题描述

已知m、n为整数，且满足下列两个条件：

    ① m、n∈{１，２，…，k}，即1≤m，n≤k

    ②（n²－m*n－m²）²＝1

你的任务是：编程输入正整数k（1≤k≤10⁹），求一组满足上述两个条件的m、n，并且使m²＋n²的值最大。例如，从键盘输入k=1995，则输出：m=987   n=1597。

输入格式

一个整数k

输出格式

满足条件且m²+n²最大的m,n

样例输入

1995

样例输出

m=987

n=1597

题解

一个斐波拉契。。。。。

先暴力打个表，把k=1..1995的m，n值打出来，找找规律，顺便检查一下暴力有没有打错。

我看到的题目没有讲清楚（不知道别的题目有没有清楚），但是看样子应该m<=n，那暴力打表就把m在前，n在后输出来，发现m的值有点像斐波拉契，但是每个数都重复了很多次，而n的值就是斐波拉契中m的下一项。所以算出m就能算出n了。

观察一下发现，对于m的值的变化，就是斐波拉契的每一项重复几次，重复的次数就是那一项的值。

于是问题就解决了。

 

#include 
     
      int k,f[1000];int main(){	int i,t;	scanf("%d",&k);	if (k==1)	{		printf("m=1\nn=1");		return 0;	}	if (k==2)	{		printf("m=1\nn=2");		return 0;	}	if (k==3)	{		printf("m=2\nn=3");		return 0;	}	f[1]=f[2]=1;  f[3]=2;	i=t=3;	while (i
      
       =k)		{			printf("m=%d\nn=%d",f[t-1],f[t]);			break;		}		i+=f[t-1];	}	return 0;}