最小的x - 题解

题解

思路

题目要求最小的正整数 $x$，使得 $n+x^2$ 是一个完全平方数。

设 $y^2=n+x^2$，移项后平方差公式直接带走：

令 $a=y-x$, $b=y+x$，则 $a\cdot b=n$。显然 $a<b$，而且因为 $x,b,y$ 都是整数，$a$ 和 $b$ 必须同奇偶（同为奇数或同为偶数）。

一旦找到满足条件的因子对 $(a,b)$，就有

为了让 $x$ 最小，需要 $b-a$ 最小。注意到 $b=n/a$，$a$ 越大，$b$ 越小，差就越小。所以我们从 $\lfloor\sqrt n\rfloor$ 开始倒序枚举 $a$，第一个合法的因子对一定对应最小的 $x$。

无解

两个同奇偶性的数相乘，结果要么是奇数，要么是 4 的倍数。所以如果 $n\equiv 2\pmod 4$，一定无解。

另外，$n=1$ 和 $n=4$ 时，唯一的因子对是 $(1,1)$ 或 $(2,2)$，算出来 $x=0$，不符合正整数要求。这两种情况直接输出 $-1$。

其余情况必然有解。

代码

1
2
3
4
5
6
7
8
9
10
11
12

long long n; cin>>n;
if (n%4==2 || n==1 || n==4) { cout<<-1; return 0; }
long long ans=-1;
for (long long a=sqrt(n); a>=1; --a) {
    if (n%a!=0) continue;
    long long b=n/a;
    if ((a%2)==(b%2) && a<b) {
        ans=(b-a)/2;
        break;
    }
}
cout<<ans;