← 完整题目索引

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)=2N(2,10)=4

C(n) 为整数对 (a,b) 的数量,使得:

  • 1abn,
  • 99N(a,b)100P(a,b),以及
  • 99P(a,b)100N(a,b)

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

C(20000000)

题解待补充

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