随笔 - 7  文章 - 27  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔档案(7)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

          这个题目就是找在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*<= 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 乔宁博 阅读(1477) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理