這個題目就是找在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
喬寧博 閱讀(1554)
評論(0) 編輯 收藏 引用