本文章由 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;
}
鲁ICP备2025150228号