2026 年省选专题系列八：数论进阶。

数论函数基础

  • 积性函数：gcd(a,b)=1 时 f(ab)=f(a)f(b)
  • 完全积性函数：任意 a,b 都有 f(ab)=f(a)f(b)

狄利克雷卷积

(f*g)(n) = Σ f(d)g(n/d)，d|n。

莫比乌斯反演

如果 F(n) = Σ f(d)，d|n，那么 f(n) = Σ μ(d)F(n/d)。

杜教筛

用于快速求积性函数前缀和，复杂度 O(n^(2/3))。

经典题型

  • gcd 求和问题
  • lcm 求和问题
  • 约数个数求和

省选一对一辅导：151 6522 2880