至尊问题「建议收藏」
大家好，又见面了，我是你们的朋友全栈君。
称号：
已知m、n为整数，且满足下列两个条件： ① m、n∈1，2,…,K,（1≤K≤10^9）
② (n^ 2－mn－m^2)^2＝1 编一程序，对给定K，求一组满足上述两个条件的m、n，而且使m^2＋n^2的值最大。比如，若K＝1995，则m＝987，n＝1597，则m、n满足条件，且可使m^2＋n^2的值最大。
输入
输入仅一行，K的值。
输出
输出仅一行，m^2＋n^2的值。
例子输入
1995
例子输出
3524578
题目字数不多。可是条件2看起来貌似有点复杂。但实际上。它也是个突破口；
由条件2：(n^ 2－mn－m^2)^2＝1
故而： (m^2 + mn－ n^2)^2＝1
继续化简：m^2＋mn－n^2＝(m＋n)^2－mn－2n^2
＝(m＋n)^2－(m＋n)n－n^2 即： (n^2－mn－m^2)^2＝[(m＋n)^2－(m＋n)n－n^2]^2
我们观察上述最后的等式，我们能够发现
n->m+n (第一个平方)
m->n,n->m+n（中间的因式）
m->n（第二个平方）
这时我们发现这是我们熟悉的斐波那契数列。这样。这一题的突破口非常明显了，m、n都是在K（包含K）之内的最大的两个满足斐波那契数列的数；
另外因为1≤K≤10^9可能m、n数字较大，即会发生数字超限，用两个数组进行平方运算以及相加运算。
#include <iostream>using namespace std;void Add(int *arrm, int *arrn, int len) //大整数相加{ int *arr = new int[len + 1]; for(int i = 0; i < len + 1; i++) arr[i] = 0; for(int i = 0; i < len; i++) { arr[i] += arrm[i] + arrn[i]; if(arr[i] >= 10) //进位 { arr[i + 1] += arr[i] / 10; arr[i] %= 10; } } int index = len; while(!arr[index]) { index--; } for(int i = index; i >= 0; i--) cout << arr[i]; cout << endl;}void Mul(int *arr, int *arr1, int len1) //大整数相乘{ for(int i = 0; i < len1; i++) { for(int j = 0; j < len1; j++) { arr[i + j] += arr1[i] * arr1[j]; if(arr[i + j] >= 10) //进位 { arr[i + j + 1] += arr[i + j] / 10; arr[i + j] %= 10; } } }}void BigData(int m, int n){ int num1 = m; int num2 = n; int *arr1 = new int[10]; int *arr2 = new int[10]; int len1 = 0, len2 = 0; while(num1) //数字数组化 { arr1[len1++] = num1 % 10; num1 /= 10; } while(num2) { arr2[len2++] = num2 % 10; num2 /= 10; } int len; if(len1 > len2) len = 2 * len1; else len = 2 * len2; int *arrm = new int[len]; int *arrn = new int[len]; for(int i = 0; i < len; i++) { arrm[i] = 0; arrn[i] = 0; } Mul(arrm, arr1, len1); //大整数相乘 Mul(arrn, arr2, len2); Add(arrm, arrn, len); //相加}void Fibo(int K){ if(K < 1) return; if(K == 1) { cout << 2 << endl; return; } int m = 1, n = 1; int p = m + n; while(p <= K) //寻找满足条件的两个Fibonacci数 { m = n; n = p; p = m + n; } if(m < 10000 || n < 10000) cout << m * m + n * n << endl; else BigData(m, n);}int main(){ int K; cin >> K; Fibo(K); return 0;}
O(∩_∩)O欢迎不吝赐教….
版权声明：本文博主原创文章，博客，未经同意不得转载。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/129191.html原文链接：https://javaforall.cn
腾讯云开发者
