【NOI1995】极值问题

问题描述

已知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 <cstdio>
int k,f[1000];
int main()
{
	int i,t;
	scanf("%d",&k);
	if (k==1)
	{
		printf("m=1
n=1");
		return 0;
	}
	if (k==2)
	{
		printf("m=1
n=2");
		return 0;
	}
	if (k==3)
	{
		printf("m=2
n=3");
		return 0;
	}
	f[1]=f[2]=1;  f[3]=2;
	i=t=3;
	while (i<k)
	{
		f[++t]=f[t-1]+f[t-2];
		if (i+f[t-1]>=k)
		{
			printf("m=%d
n=%d",f[t-1],f[t]);
			break;
		}
		i+=f[t-1];
	}
	return 0;
}