作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 464 Möbius function and
时间Thu Apr 17 04:31:48 2014
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)。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.2.129.155
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/puzzle/M.1397680312.A.62F.html