d264 - 极值问题

🔗 前往 ZeroJudge 原題

題目描述

題目要求找到兩個整數 m 和 n，滿足 m <= n，且 (nn - mn - mm)^2 = 1，並使 mm + n*n 的值最大。輸入 k，表示 m 和 n 的上限。

解題思路

題目給定的等式 (nn - mn - mm)^2 = 1，可以推導出 nn - mn - mm = 1 或 nn - mn - mm = -1。 由於 m 和 n 都是正整數，nn - mn - mm = -1 無解。因此，我們只需要考慮 nn - mn - m*m = 1。 將等式變形，得到 n^2 - mn - m^2 = 1。 這個等式可以看作是費波那契數列的變形。當 m = 1 時，n^2 - n - 1 = 1，解得 n^2 - n - 2 = 0，(n-2)(n+1) = 0，n = 2。 當 m = 2 時，n^2 - 2n - 4 = 1，解得 n^2 - 2n - 5 = 0，無整數解。 當 m = 3 時，n^2 - 3n - 9 = 1，解得 n^2 - 3n - 10 = 0，(n-5)(n+2) = 0，n = 5。 可以發現，m 和 n 滿足費波那契數列的關係。程式碼預先計算了前 40 個費波那契數，然後遍歷這些數，找到滿足 n <= k 的最大 m 和 n。

複雜度分析

• 時間複雜度: O(k) (實際上是 O(40)，因為預先計算了費波那契數列)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int a[40]={1,1,2};
int main(){
	int n,i;
	for(i=2;i<40;++i){
		a[i]=a[i-1]+a[i-2];
	}
	while(scanf("%d",&n)>0){
		for(i=0;a[i]<=n;++i){}
		printf("%d %d\n",a[i-2],a[i-1]);
	}
}