HDU 4206 Treasure Map

2895 ワード

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=4206
一つの数nをあげます.b^2-a^2==nを聞きます.条件を満たすaとbを求めます.複数の出力が一番小さいのがあれば、ないなら、IMPOSSIBLEを出力します.
 
b^2-a^2=(b-a)*(b+a)= p*q=n
1<====10^9ですので、今は1からルート番号10^9までを列挙します.
a=(q-p)/2b=(q+p)/2そのうち(q-p)も(q+p)も偶数で、n%p==0(剪定用)
そして列挙する時に一番小さいaを取ります.
#include <iostream>
#include <cmath>
using namespace std;

const int INF = 1<<30;
int main()
{
int t;
int n;
int i, j;
int p, q;
int a, b;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
a = INF;
for (p = 1; p <= (int)sqrt(double(n)); p++)
{
if (n % p == 0 && (n/p - p) % 2 == 0)
{
q = n/p;
if (a > (q-p)/2)
{
a = (q-p)/2;
b = (q+p)/2;
}
}
}
if (a == INF)
{
puts("IMPOSSIBLE");
}
else
{
printf("%d %d
", a, b);
}
}
return 0;
}