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

· · 题解

题目：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|}) 。

代码：

#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}) 这样就能过了……