本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-22 13:20:26

题目
考察：数学，递推打表。

20~60 分做法：

$n,m$ 两数均暴力枚举，时间复杂度为 $O(n^2)$，无法通过 $k\le 10^8$ 的数据。

100 分做法 1：

做法 $1$ 需要一些数学知识，题中给的式子：
$$\lvert n^2-mn-m^2\rvert=1$$ 拆开绝对值符号，得： $$\begin{cases}n^2-mn-m^2=1\n^2-mn-m^2=-1\end{cases}$$ 移项，得：
$$\begin{cases}-m^2-nm+(n^2-1)=0\-m^2-nm+(n^2+1)=0\end{cases}$$ 这样我们就得到两个方程，我们可以枚举 $n$，也可以枚举 $m$。
根据一元二次方程求根公式，得： $$\begin{cases}a=-1,b=-n,c=n^2-1\=-1,b=-n,c=n^2+1\end{cases}$$ 那么（注：$\Delta=b^2-4ac$）：
$$\begin{cases}\Delta=(-n)^2-4\times(-1)\times(n^2-1)=3n^2-4\\Delta=(-n)^2-4\times(-1)\times(n^2+1)=3n^2+4\end{cases}$$ 那么我们得到四个可能的根： $$\begin{cases}m_1=\frac{(-b)+\sqrt\Delta}{2a}=-\frac{\sqrt{3n^2-4}+n}{2}\\m_2=\frac{(-b)-\sqrt\Delta}{2a}=\frac{\sqrt{3n^2-4}-n}{2}\\m_3=\frac{(-b)+\sqrt\Delta}{2a}=-\frac{\sqrt{3n^2+4}+n}{2}\\m_4=\frac{(-b)-\sqrt\Delta}{2a}=\frac{\sqrt{3n^2+4}-n}{2}\end{cases}$$ 但要成为一个真正的根，还要满足以下条件：

• $\Delta\ge0$
• $m\in\{1,2,\dots,k\}$

最后在这些根里面找到使 $n^2+m^2$ 最大的数即可。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
int k,ans,mxn,mxm;
signed main(){
	k=read();
	for(reg int n=1;n<=k;++n){
		reg int a=-1,b=-n,c=-1+n*n,c2=1+n*n;
		reg int delta=b*b-4*a*c,delta2=b*b-4*a*c2;
		reg double sq=sqrt(delta),sq2=sqrt(delta2);
		reg double num1=(-b+sq)\/(2*a),num2=(-b-sq)\/(2*a);
		reg double num3=(-b+sq2)\/(2*a),num4=(-b-sq2)\/(2*a);
		if(num1==(int)num1&&ans<n*n+num1*num1&&num1>0&&num1<=k){
			ans=n*n+num1*num1;
			mxn=n;
			mxm=num1;
		}
		if(num2==(int)num2&&ans<n*n+num2*num2&&num2>0&&num2<=k){
			ans=n*n+num2*num2;
			mxn=n;
			mxm=num2;
		}
		if(num3==(int)num3&&ans<n*n+num3*num3&&num3>0&&num3<=k){
			ans=n*n+num3*num3;
			mxn=n;
			mxm=num3;
		}
		if(num4==(int)num4&&ans<n*n+num4*num4&&num4>0&&num4<=k){
			ans=n*n+num4*num4;
			mxn=n;
			mxm=num4;
		}
	}
	printf("m=%d\nn=%d",mxm,mxn);
	return 0;
}

100 分做法 2：

我们发现，这些数可能是一个有规律的数列。
那么我们可以通过打表寻找规律。
打表代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
int k,ans,mxn,mxm;
inl void f(int i){
	for(reg int y=i;y>=1;--y)
		for(reg int x=i;x>=1;--x)
			if(abs(x*x-x*y-y*y)==1){
				printf("i=%d x=%d y=%d\n",i,y,x);
				return;
			}
}
signed main(){
	k=read();
	for(reg int i=1;i<=k;++i) f(i);
	return 0;
}

结果：

可以看到，最后的结果酷似斐波那契数列，那我们就可以写代码了！
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 214748364721474836
using namespace std;
inl int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
inl void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>=10) write(x\/10);
	putchar(x%10^48);
}
#define K 114514
int k,a[K],i;
signed main(){
	k=read();
	a[1]=a[2]=1;
	for(i=3;a[i-1]<=k;++i) a[i]=a[i-1]+a[i-2];
	printf("m=%d\nn=%d",a[i-3],a[i-2]);
	return 0;
}