题目：P11496 [ROIR 2019 Day 1] 完全平方

题意

给出一个整数 $k$ ，寻找 $i, j \in \mathbb{N}$ 使得 $k+i^2=j^2$ ，求 $j$ 的最小值。若没有满足的取值，则输出 none 。

思路

对于 $k=0$ 的情况，原方程可化为 $i^2=j^2$ ，当 $i=0$ 时 $j$ 取得最小值 $0$ 。

对于 $k \neq 0$ 的情况，我们可以把原方程整理如下：

$$k=j^2-i^2$$

$$k=(j+i)(j-i)$$

令 $p=i+j$ ， $q=j-i$ ，那么 $ i=\frac{p-q}{2}$ ，$ j=\frac{p+q}{2}$ 。

我们可以从 $1$ 到 $\sqrt{|k|}$ 的范围内遍历 $k$ 的所有因数，判断此时分解出来的因数 $p,q$ 是否能化为 $k=pq=(j+i)(j-i)$ 的形式，如果可以的话就更新 $j$ 的最小值，且这个方法正负数同理。

时间复杂度 $\text{O}(\sqrt{|k|})$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const ll inf=1e18;
inline ll read(){
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
signed main(){
    ll n=read(),ans=inf;
    if(n==0){
        puts("0");return 0;
    }
    for(ll p=sqrt(abs(n));p>=1;--p){
        ll q=n/p;
        if(p*q!=n) continue;
        if(abs(p+q)%2) continue;
        ans=min(ans,abs(p+q)/2);//算数平方根为正 eg. p=1, q=-5 & p=-1, q=5 可以一起计算
    }
    if(ans==inf) puts("none");
    else printf("%lld",ans);
    return 0;
}

闲话

想了很久怎么快速的分解因数，没想到 $\text{O}(\sqrt{|k|}) (-10^{12} \le k \le 10^{12})$ 这样就能过了……