2011年7月20日 星期三

10299 - Relatives

題目原文

難度
☆☆

問題
給你1個正整數n,請你找出有多少小於n的正整數與n互質。2個數互質是指這2個數除了1之外,沒有其他的公因數。

* 中文翻譯:Lucky 貓


Input
每組測試資料一列,含有一正整數 n(n <= 1,000,000,000)。當n=0代表輸入結束。

Output
對每組測試資料,請輸出有多少小於n的正整數與n互質。


Sample Input
7
12
0

Sample Output
6
4


解法
若一個小於n的數要與n互質,則這個數就不能擁有跟n相同的質因數。
假設n = 90 = 2 * 32 * 5,即90的質因數有2、3、5,本題要的數不能有這三個質因數。

我們可以利用排容原理求出小於n且擁有與n相同的質因數的數個數:
(能被2除盡的個數 + 能被3除盡的個數 + 能被5除盡的個數)
 - (能同時被2、3除盡的個數 + 能同時被3、5除盡的個數 + 能同時被2、5除盡的個數)
+ 能同時被2、3、5除盡的個數

以n=90為例,與n擁有共同因數的數共有:
( 45 + 30 + 18 ) - ( 15 + 6 + 9 ) + 3 = 66 個
而我們要找的是與90互質的個數,即90 - 66 = 24。

我們可以化簡上式導出一通式:


因此小於n且與n互質的所有數的個數為:


其中A1~Ak為n的質因數,此公式稱作尤拉商數函數 (Euler's Totient Function)。

1 則留言:

  1. hi,
    我覺得應該要用這個form:

    n ÷ p1 × (p1-1) ÷ p2 × (p2-1) ÷ … ÷ pk × (pk-1)

    這樣子n可以直接用int去代

    不需要用double

    而且也避免浮點數誤差的問題(雖然我不知道這題會不會有這問題XD)

    我是參考這邊:
    http://www.csie.ntnu.edu.tw/~u91029/Prime.html#a5

    回覆刪除