← 完整题目索引

PROJECT EULER · #0464

莫比乌斯函数和区间

Möbius Function and Intervals

仅题目 · 待解原题 ↗

莫比乌斯函数,表示为μ(n),定义为:

  • μ(n)=(−1)ω(n) 如果 n 是无平方因子的(其中 ω(n) 是 n 的不同质因数的数量)
  • 如果 n 不是无平方因子的,则μ(n)=0。

令 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≤n,
  • 99⋅N(a,b)≤100⋅P(a,b),以及
  • 99⋅P(a,b)≤100⋅N(a,b)。

例如,C(10)=13、C(500)=16676 和 C(10000)=20155319。

求C(20000000)。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。