HDU-4143 A Simple Problem
2191 ワード
A Simple Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1959 Accepted Submission(s): 518
Problem Description
For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2.
Input
The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).
Output
For each integer n, please print output the x in a single line, if x does not exit , print -1 instead.
Sample Input
2 2 3
Sample Output
-1 1
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1959 Accepted Submission(s): 518
Problem Description
For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2.
Input
The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).
Output
For each integer n, please print output the x in a single line, if x does not exit , print -1 instead.
Sample Input
2 2 3
Sample Output
-1 1
/*
:
n, x y^2 = n +x^2 , (y-x)*(y+x)=n, y-x , y-x y+x;
*/
// :
#include<stdio.h>
int main()
{
int T,i,a,n,tmp,ans;
scanf("%d",&T);
while(T--)
{
ans=0x7fffffff;
scanf("%d",&n);
for(i=1;i*i<n;++i)
{
if(n%i==0)
{
a=n/i;
if(((a+i)&1)==0&&((a-i)&1)==0)
{
tmp=(a-i)>>1;
if(tmp<ans)
ans=tmp;
}
}
}
if(ans!=0x7fffffff)
printf("%d
",ans);
else
printf("-1
");
}
return 0;
}
/*
:--- : x , y-x y+x , sqrt(n)
#include <stdio.h>
#include <math.h>
int main()
{
int T,i,flag,n;
scanf("%d",&T);
while(T--)
{
flag=0;
scanf("%d",&n);
for(i=sqrt(n);i>=1;--i)
{
if(n%i==0&&(n/i-i)%2==0&&n/i!=i)
{
flag=1;
break;
}
}
if(flag)
printf("%d
",(n/i-i)/2);
else
printf("-1
");
}
return 0;
}*/