[中譯] ProjectEuler 464 Möbius function and

作者: tml (流刑人形)   2014-04-17 04:31:48
464. Möbius function and intervals
http://projecteuler.net/problem=464
莫比烏斯函數,記作μ(n)定義如下:
 ‧μ(n) = (-1)^ω(n),如果n沒有任何平方數因子,其中ω(n)為n的質因數個數。
 ‧μ(n) = 0,如果n有平方數因子。
令P(a,b)為閉區間[a, b]裡的正整數n中,符合μ(n) = 1的個數。
令N(a,b)為閉區間[a, b]裡的正整數n中,符合μ(n) = -1的個數。
例如,P(2,10) = 2以及N(2,10) = 4。
令C(n)為正整數對(a,b)符合下列規則的個數:
 ‧1≦a≦b≦k
 ‧99N(a,b)≦100P(a,b)
 ‧99P(a,b)≦100N(a,b)
例如,C(10) = 13,C(500) = 16676以及C(10000) = 20155319。
請求出C(20000000)。

Links booklink

Contact Us: admin [ a t ] ucptt.com