===

Index

• 积性函数简介
• 狄利克雷卷积
• 例题
  • lcm求和
  • gcd求和

积性函数简介

考虑一个定义域为正整数的函数f，对于任意两个互质的正整数a,b, 均满足 f(a,b)=f(a)*f(b), 则函数f被称为积性函数。

如果对于任意两个正整数a,b，都有 f(ab)=f(a)*f(b) ，函数f也被称为完全积性函数

性质

• 对于任意积性函数 f(1)=1
• 欧拉函数为积性函数，当n>1时，1..n中与n互质的整数和为 n*ph(n)/2
• 莫比乌斯函数mu 是积性函数
  • mu(n) = 1 // n = 1
  • mu(n) = (-1)^k // n = p1p2…pk, n的质因数分解中次数均为1
  • mu(n) = 0 其他情况
• 若f(n),g(n)均为积性函数，则 h(n)=f(n)g(n)也是积性函数
• 若f(n)为积性函数,则函数 g(n)=sum(f(d)) (d=1…n且,d整除n)

• sum(mu(d), d

  n) = [n = 1] // n = 1 时为1，其余为0

狄利克雷卷积

例题

lcm求和

luogu p1829

给定n,m, 求 sum(i=1..n)sum(j=1..m) lcm(i,j) 的值，模 20101009。

• 1 <= n, m <= 1e7

时间复杂度 O(n + m)

gcd求和