HDU 4143 A Simple Problem(枚举)

题目链接

题意 : 就是给你一个数n,让你输出能够满足y^2 = n +x^2这个等式的最小的x值。

思路 : 这个题大一的时候做过,但是不会,后来学长给讲了,然后昨天比赛的时候二师兄看了之后就敲了,我也想了一会儿才想起来,真是惭愧啊。。。。。

其实就是将上边那个式子变一下:(y-x)*(y+x) = n ,然后接下来就去枚举(y-x)的值,因为手算了几组数据,发现当这个值越靠近√n时,x的值越小,其实看这个等式也可以看出来,所以枚举的时候从√n这里开始往下枚举就行,然后再看(y-x)+(y+x) = 2*y ,所以你枚举出这个(y-x)的值再用n除以(y-x)得到一个数,这两个数加起来得是2的倍数。

 //
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h> using namespace std; int main()
{
int T ,n;
scanf("%d",&T) ;
while(T--)
{
scanf("%d",&n) ;
int temp = sqrt(n) ,i;
for(i = temp ; i >= ; i--)
{
if(n % i == && n/i != i && (n/i+i) % == )
{
printf("%d\n",(n/i+i)/-i) ;
break ;
}
}
if(i == ) printf("-1\n") ;
}
return ;
}
上一篇:【C++】__gcd(x,y)函数


下一篇:求最大公约数的欧几里得算法与其伪代码