【数论】HDU 4143 A Simple Problem

题目内容

给出一个正整数\(n\)，找到最小的正整数\(x\)，使之能找到一个整数\(y\)，满足\(y^2=n+x^2\)。

输入格式

第一行是数据组数\(T\)，每组数据有一个整数\(n\)。

输出格式

输出\(T\)行，表示\(x\)，若找不到答案输出\(-1\)。

数据范围

\(0\le n\le 10^9\)

样例

2

2

3

样例输出

-1

1

思路

A Not Simple Problem

原式变形一下：

\(n=(y+x)(y-x)\)

因此找到\(n\)的两个因子，设为\(a_1=y+x\)，\(a_2=y-x\)。

此时\(a_1-a_2=2x\)，找到差最小值即可。

需要满足的条件:

\(x\)是正数 \(\Rightarrow a_1>a_2\)

\(x\)是整数 \(\Rightarrow (a_1-a_2)\%2=0\)

\(y\)是整数 \(\Rightarrow (a_1+a_2)\%2=0\)

代码

#include<bits/stdc++.h>

using namespace std;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n;

        scanf("%d",&n);

        int ans=0x3f3f3f3f;

        bool flag=false;

        for(int i=1;i<=sqrt(n);i++){

            if(n%i==0&&(i+n/i)%2==0&&(n/i-i)%2==0&&i!=n/i&&(n/i-i)>0){

                flag=true;

                if(n/i-i<ans)ans=n/i-i;

            }

        }

        if(flag)printf("%d\n",ans/2);

        else printf("-1\n");

    }

    return 0;

}

巴特西