• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

莫比乌斯反演入门

admin

11月 28, 2021

大部分从oiwiki上看到的,有误欢迎大佬斧正

积性函数

定义

(f(x)f(y)=f(xy))((x,y)=1) ,则 (f(x))为积性函数。

性质

(f(x))(g(x))均为积性函数,则以下函数也为积性函数:

[egin{align}&h(x)=f^p(x)\
&h(x)=f(x^p)\
&h(x)=f(x)g(x)\
&h(x)=sum_{dmid x}f(d)g(x/d)
end{align}]

常见积性函数

  1. 约数函数 (sigma_k(n)=sum_{dmid n}d^k) 表示n的约数的k次幂之和
  2. 约数和函数 (sigma(n)=sum_{dmid n}d) 表示n的约数和 ((3.1,k=1))
  3. 约数个数函数 ( au(n)=sum_{dmid n}1) 表示n的约数个数 通常也写作(d(n))
  4. 欧拉函数 (phi(n)=sum_{i=1}^{n-1}(i,n)=1) 表示([1,n-1]中与n互素的数的个数)
  5. 莫比乌斯函数 $$mu(n)=egin{cases}1 & n=1 & exists d: d^2mid n(-1)^{omega(n)} & otherwiseend{cases}$$ (omega(n)mbox{表示n的不同素因子个数}) 与不变函数在迪利克雷卷积中互为逆元
  6. 单位元 (epsilon(n)=[n=1]) 迪利克雷卷积中的单位元
  7. 幂函数 (id_k(n)=n^k)
  8. 单位函数 (id(n)=n)
  9. 不变函数 (1(n)=1)
    最后三个为完全积性函数

迪利克雷卷积

定义

定义两个数论函数(f,g)的迪利克雷卷积为

[(f*g)(n)=sum_{dmid n}f(d)g(n/d)
]

性质

  1. 交换律
  2. 结合律

常见积性函数卷积

  1. (epsilon=mu*1 Leftrightarrow epsilon(n)=sum_{dmid n}mu(d)) 单位元等于莫比乌斯函数和不变函数的卷积
  2. (d=1*1 Leftrightarrow d(n)=sum_{dmid n}1*1) 约数个数函数等于不变函数与不变函数作卷积
  3. (sigma=d*1 Leftrightarrow sigma=sum_{dmid n}d) 约数和函数等于约数个数函数和不变函数作卷积
  4. (phi=id*mu Leftrightarrow phi(n)=sum_{dmid n}dmu(n/d) Leftrightarrow frac{phi(n)}{n}=sum_{dmid n}frac{mu(d)}{d})
  5. (id=phi*1),可由前面式子推出,将4式代入,右边=(mu*1*id),莫比乌斯函数和不变函数互为逆元,卷积为单位元则最后结果为单位函数id

单位元证明

(epsilon(n)=sum_{dmid n}mu(d)),根据唯一分解定理(n=prod_{i=1}^q p_i^{r_i})
已知当n有平方因子时,(mu(n)=0),此时对答案无贡献,我们不妨将(nmbox{转换为}n’=prod_{i=1}^q p_i)
那么约数就是({p_1,p_2,…p_q})的组合,$$epsilon(n)=sum_{dmid n}mu(d)=sum_{dmid n’}mu(d)=sum_{i=0}qC(q,i)(-1)i=0,ngt 1$$
最后一步由二项式定理的来,((1+(-1))^k=0)

补充结论

([gcd(i,j)=1] Leftrightarrow sum_{dmid gcd(i,j)}mu(d))十分有用!!!

莫比乌斯反演

公式

(f(n),g(n))是两个数论函数,如果有

[f(n)=sum_{dmid n}g(d)
]

对于(g(n))有反演公式

[g(n)=sum_{dmid n}mu(d)f(n/d)
]

证明

  1. 暴力证明

将反演公式右边的(f(n/d))由原式子替换,得到

[sum_{dmid n}mu(d)sum_{kmid frac{n}{d}}g(k)
]

这时d在第一个和式里面的规则是(n=rd),k在第二个和式的规则是(n/d=qk),我们交换求和顺序,得到

[sum_{kmid n}g(k)sum_{dmid frac{n}{k}}mu(d)
]

在第二个和式里,由之前的单位函数证明可以得知仅有(frac{n}{k}=1)时不为0,即上式当且仅当(n=k)时不为0,此时$$sum_{kmid n}g(k)sum_{dmid frac{n}{k}}mu(d)=g(n)$$

  1. 卷积证明

(f=g*1,mbox{那么}f*mu=g*1*mu mbox{,而常数函数和莫比乌斯函数互为逆元,卷积得单位元,因此}f*mu=g*1*mu=g)

点点杂项公式

约数相关

  1. [d(ij)=sum_{xmid i}sum_{ymid j}[gcd(i,j)=1],洛谷p3327
    ]

发表评论

您的电子邮箱地址不会被公开。