U610469 牢高的压轴题

题目背景

这是 ooliver 与 Deepseek 的聊天记录：

---老高太强了，这怎么玩？必须削弱！

Deepseek（已深度思考114514秒）∧
有的兄弟，有的。

---那这题咋写?

Deepseek（已深度思考0秒）∨
系统繁忙，请稍后再试。

题目描述

周清时间到了，来看看老高为你量身定制的压轴题吧：

已知 $x^2+xy+y^2=z$ $(x,y,z \in Z)$ ，并且现在告诉你 $z$ 的值，求 $x,y$ 的值。

如果有多组解，输出 $x$ 最小的那一组，如果有多组 $x$ 最小的解决，输出 $y$ 最小的那一组；如果无解，输出 No Answer。

输入格式

一行，一个整数 $z$。

输出格式

一行。

若有解，输出两个整数 $x,y$，用空格隔开。

若无解，输出果无解，输出 No Answer。

输入输出样例 #1

输入 #1

12

输出 #1

-4 2

输入输出样例 #2

输入 #2

2022

输出 #2

No Answer

说明/提示

题解

这题是一道数学与数论结合的题目，题解只展示求解过程，层层递进的思考过程不予展示。

令 $z=2^i·l(2 \nmid l)$,

不难发现，当 $(2 \nmid i)$ 时，
令 $x=2^{\frac{i-1}{2}}·m，y=2^{\frac{i-1}{2}}·n.$
原方程可列为 $m^2+mn+n^2=2l$
此时分析奇偶，不难发现：
当 $m,n$ 同为奇或一奇一偶时，$m^2+mn+n^2$ 的值为奇数，
当 $m,n$ 同为偶时，$m^2+mn+n^2$ 的值为四的倍数，
又 $4 \nmid 2l$ 且 $2 \mid 2l$，
$∴$ 此时原方程无解，输出No Answer即可.

而发现，当 $(2 \mid i)$ 时，
令 $x=2^{\frac{i}{2}}·m，y=2^{\frac{i}{2}}·n.$
原方程可列为 $m^2+mn+n^2=l$
根据上方的奇偶分析可以知道，在这种情况下需要对 $m,n$ 的值进行枚举.
$∵m^2+mn+n^2=l$
$∴(m+\frac{1}{4}n)^2+\frac{3}{4}n^2=l$
$∵(m+\frac{1}{4}n)^2≥0$
$∴\frac{3}{4}n^2≥l$
$∴-\frac{2\sqrt{3n}}{3}≤n≤\frac{2\sqrt{3n}}{3}$
同理，$∴-\frac{2\sqrt{3n}}{3}≤m≤\frac{2\sqrt{3n}}{3}$
所以将 $m$ 的值枚举并解关于 $n$ 的一元二次方程即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int z,x,y;
    cin>>z;
    int p=0,q=z;
    while(q%2==0) q/=2,p++;
    if(p%2==1) cout<<"No Answer";
    else{
        for(int i=ceil(-(2.0*sqrt(3*q))/3.0);i<=int(2.0*sqrt(3*q)/3.0);i++){
            int m=i;
            int a=1,b=m,c=m*m-q;
            int delta=b*b-4*a*c;
            if(delta<0||sqrt(delta)*sqrt(delta)!=delta) continue;
            int n=INT_MAX;
            if(int(-b-sqrt(delta))%2==0) n=min(int(-b-sqrt(delta))/2,n);
            else if(int(-b+sqrt(delta))%2==0) n=min(int(-b+sqrt(delta))/2,n);
            else continue;
            x=m*pow(2,p/2),y=n*pow(2,p/2);
            cout<<x<<" "<<y;
            return 0;
        }
        cout<<"No Answer";
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int z,x,y;
    cin>>z;
    int p=0,q=z;
    while(q%2==0) q/=2,p++;
    if(p%2==1) cout<<"No Answer";
    else{
        for(int i=ceil(-(2.0*sqrt(3*q))/3.0);i<=int(2.0*sqrt(3*q)/3.0);i++){
            int m=i;
            int a=1,b=m,c=m*m-q;
            int delta=b*b-4*a*c;
            if(delta<0||sqrt(delta)*sqrt(delta)!=delta) continue;
            int n=INT_MAX;
            if(int(-b-sqrt(delta))%2==0) n=min(int(-b-sqrt(delta))/2,n);
            else if(int(-b+sqrt(delta))%2==0) n=min(int(-b+sqrt(delta))/2,n);
            else continue;
            x=m*pow(2,p/2),y=n*pow(2,p/2);
            cout<<x<<" "<<y;
            return 0;
        }
        cout<<"No Answer";
    }
    return 0;
}