这个题目就是找在1~N之间互质的三个正整数x、y、z，并满足x^2+y^2=z^2，判断这样的数有多少对，以及跟1~N中与这些互质正整数无关的正整数的个数。
其实比较关键的是对上面那个式子 x^2+y^2=z^2 进行变形，减少一个变量为
(r^2-s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2，
这样只有两个变量存在，可以减少一轮循环。于是题目就变成了找这样的r和s，当r*r + s*s <= n时，
z = r*r + s*s;
y = max(r*r - s*s, 2*r*s);
x = min(r*r - s*s, 2*r*s);
此时，如果x、y、z互质，满足条件的正整数组计数就加1，同时把所有与这些数相关的数组位标记为1，
for (i = 1; i*z <= n; i++)
{
flag[i*x] = flag[i*y] = flag[i*z] = 1;
}
输出第二个结果的时候，即为输出标志数组中值为0的元素个数。
for (i = 1; i <= n; i++)
{
if (!flag[i])/**//*The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N */
num++;
}
虽然在题目中说到N最大为1，000，000 ，但是poj测试数据大概在2000内。使用2001大小的标记数组就可以过。
posted on 2010-01-04 11:04
乔宁博 阅读(1511)
评论(0) 编辑 收藏 引用