问题 G: 极值问题

题目描述
修罗王：“等了这么久，怎么攻城的魔法炮还没有响？”

邪狼满头大汗：“这魔法炮使用起来太复杂了，每次操作都需要输入验证码，首先它会产生一个正整数k，你要根据这个数输入正确的m和n两个整数才能发射。”

修罗王：“这是谁设计的炮啊，不考虑客户体验，界面友好性吗？让我来看看…”

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

（1）m、n属于{1，2，…，k}，即1≤m，n≤k

（2）（n2－mn－m2）2=1

你的任务是：根据输入的正整数k(1≤k≤109)，求一组满足上述两个条件的m、n，并且使m2+n2的值最大。例如从键盘输入k=1995，则输出m=987 ，n=1597。
输入
一个整数k
输出
输出m和n的值
样例输入 Copy
1995
样例输出 Copy
987 1597

题意就是求m和n 其实就是推一下下面这个式子


（n2－mn－m2）2


= (m2+mn-n2) 2


=((m+n)2-mn-2*n2)2


=((m+n)2-n*(m-n)-n2)2


因为外面有平方所以n*(m-n)==n*(m+n)
就可以推出来递归式
n=n+m；
m=n；

所以就转化成一个斐波那契了；

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#define ll long long int
#define inf 0x3f3f3f3f
const int mod=998244353;
using namespace std;
const int maxn=2e5+10;
const double pi = 3.1415926535898;
const int dx[9]={0,1,1,2,2,-1,-1,-2,-2};
const int dy[9]={0,2,-2,1,-1,2,-2,1,-1};

bool isprime[10000000];
ll n,m,sum,p,t,h,cnt,q,num;
ll Prime[maxn],s1,s2,p1,p2;
//char str[110][100],s[maxn],ss[maxn];
ll num_prime[maxn],prime[maxn],dashu[maxn];

void f(){//打表 
	prime[1]=1;
	prime[0]=1;
	for(int i=2;i<=maxn;i++)
	{
		if(prime[i-1]+prime[i-1]>1e9+7) break;
		prime[i]=prime[i-1]+prime[i-2];
	}
}
int main(){
	f();
	cin>>n;
	for(int i=1;i<=maxn;i++)
	{
		if(prime[i]>=n){
		p=i;
		break;
		}
	}
	cout<<prime[p-2]<<" "<<prime[p-1]<<endl;
	
	return 0;
}