【数论】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;
}
上一篇:eclipse配置maven + 创建maven项目


下一篇:[CC150] 八皇后问题