推 sleep123:其實展開來看就是排容，只不過高斯的另外算 08/15 13:16
→ sleep123:有學過數論這是個不錯的解法 08/15 13:16
※ 引述《webber6418 (小超)》之銘言：
: 類題演練2:
: 在101到500之間共有400個正整數，其中和12互質的數共有幾個?
: Ans:134
這題也可以採用尤拉公式, 但最後幾個數需分開討論.
首先, 觀察 12 = 2^2 x 3 (標準分解式),
互質的直觀意義是組成份子 (質因數) 皆不同.
注意不大於 100 和 500 的正整數中最大的 6 的倍數分別是 96 和 498.
所以不大於 96 的正整數中與 12 互質的有 96(1 - 1/2)(1 - 1/3) = 32 個,
加上 97 在內不大於 100 的正整數中與 12 互質的有 33 個 ---(1)
同理, 不大於 498 的正整數中與 12 互質的有 498(1 - 1/2)(1 - 1/3) = 166 個.
加上 499 在內不大於 500 的正整數中與 12 互質的有 167 個 ---(2)
(1) - (2) 得到 134 個.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.19.115.242