P9783 [ROIR 2020 Day1] 平方 题解

· · 题解

因为 x^2-y^2=n，所以 (x+y)(x-y)=n。x+y 和 x-y 明显同号，所以 n 要么得是奇数，要么能被 4 整除，否则它就不能被分成 (x+y)(x-y)。

当 n 是奇数，考虑构造 x+y=n,x-y=1。两式相加，得到 2x=n+1，两式相减，得到 2y=n-1。所以当 n 是奇数，其中一个答案就是 x=\frac{n+1}{2},y=\frac{n-1}{2}。但是，题面又规定 x,y 必须是正整数，所以 n 为 1 时无解，需要特判。

当 n 能被 4 整除，先抛开 n=0 的情况，考虑构造 x+y=\frac{n}{2},x-y=2。同样的方法，计算出 x=\frac{\frac{n}{2}+2}{2}=\frac{n}{4}+1,y=\frac{\frac{n}{2}-2}{2}=\frac{n}{4}-1。因为 x,y 得是正整数，所以 n=4 时无解。而当 n=0 时，只需要 x=y 即可，所以此时输出两个相等的数就行了。

综上，可以先判断 n 是否为 0，为 0 时输出两个相同的数；然后判断 n 是否是 1 或 4，如果是则无解；接下来判断 n 是否是不能被 4 整除的偶数，是则无解；最后判断 n 是奇数还是偶数，然后输出相应的 x,y 的解。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    long long n;cin>>n;
    if(n==0)cout<<"Yes\n114514 114514",exit(0);//n 为 0 的情况
    if(n==1||n==4)cout<<"No",exit(0);//n 为 1 或 4 的特殊情况
    if(n%4==2)cout<<"No",exit(0);//n 不是奇数也不是 4 的倍数的情况
    if(n%2)cout<<"Yes\n"<<(n+1)/2<<" "<<(n-1)/2;//n 是奇数的情况
    else cout<<"Yes\n"<<n/4+1<<" "<<n/4-1;//n 是 4 的倍数的情况
    return 0;
}