ProjectEuler 464 Möbius function and - 拼圖

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)。

--