HDU 4206 Treasure Map
题目：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<=n<=10^9,现在我们只要枚举p从1到根号10^9,
a = (q-p)/2;
b = (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\n", a, b);
}
}
return 0;
}
1、保定招聘 php程序员 php技术总监 php实习生
2、图解HTTP-1.web和网络基础
3、GPFS介绍
4、ubuntu16.04LTS更换阿里源
5、error LNK2019: 无法解析的外部符号 _WinMain@16，该符号在函数 ___tmainCRTStartup 中被引用