问题 G: 极值问题

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

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

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

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

(1)m、n属于{1,2,…,k},即1≤m,n≤k

(2)(n2-mn-m22=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-m22


= (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;
}