這個(gè)題目就是找在1~N之間互質(zhì)的三個(gè)正整數(shù)x、y、z，并滿足x^2+y^2=z^2，判斷這樣的數(shù)有多少對(duì)，以及跟1~N中與這些互質(zhì)正整數(shù)無關(guān)的正整數(shù)的個(gè)數(shù)。
其實(shí)比較關(guān)鍵的是對(duì)上面那個(gè)式子 x^2+y^2=z^2 進(jìn)行變形，減少一個(gè)變量為
(r^2-s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2，
這樣只有兩個(gè)變量存在，可以減少一輪循環(huán)。于是題目就變成了找這樣的r和s，當(dāng)r*r + s*s <= n時(shí)，
z = r*r + s*s;
y = max(r*r - s*s, 2*r*s);
x = min(r*r - s*s, 2*r*s);
此時(shí)，如果x、y、z互質(zhì)，滿足條件的正整數(shù)組計(jì)數(shù)就加1，同時(shí)把所有與這些數(shù)相關(guān)的數(shù)組位標(biāo)記為1，
for (i = 1; i*z <= n; i++)
{
flag[i*x] = flag[i*y] = flag[i*z] = 1;
}
輸出第二個(gè)結(jié)果的時(shí)候，即為輸出標(biāo)志數(shù)組中值為0的元素個(gè)數(shù)。
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測試數(shù)據(jù)大概在2000內(nèi)。使用2001大小的標(biāo)記數(shù)組就可以過。
posted on 2010-01-04 11:04
喬寧博 閱讀(1550)
評(píng)論(0) 編輯 收藏 引用