大部分从oiwiki上看到的，有误欢迎大佬斧正
积性函数
定义
若 (f(x)f(y)=f(xy))且((x,y)=1) ，则 (f(x))为积性函数。
性质
若(f(x))和(g(x))均为积性函数，则以下函数也为积性函数：
常见积性函数
- 约数函数 (sigma_k(n)=sum_{dmid n}d^k) 表示n的约数的k次幂之和
- 约数和函数 (sigma(n)=sum_{dmid n}d) 表示n的约数和 ((3.1,k=1))
- 约数个数函数 ( au(n)=sum_{dmid n}1) 表示n的约数个数 通常也写作(d(n))
- 欧拉函数 (phi(n)=sum_{i=1}^{n-1}(i,n)=1) 表示([1,n-1]中与n互素的数的个数)
- 莫比乌斯函数 $$mu(n)=egin{cases}1 & n=1 & exists d: d^2mid n(-1)^{omega(n)} & otherwiseend{cases}$$ (omega(n)mbox{表示n的不同素因子个数}) 与不变函数在迪利克雷卷积中互为逆元
- 单位元 (epsilon(n)=[n=1]) 迪利克雷卷积中的单位元
- 幂函数 (id_k(n)=n^k)
- 单位函数 (id(n)=n)
- 不变函数 (1(n)=1)
最后三个为完全积性函数
迪利克雷卷积
定义
定义两个数论函数(f,g)的迪利克雷卷积为
性质
- 交换律
- 结合律
常见积性函数卷积
- (epsilon=mu*1 Leftrightarrow epsilon(n)=sum_{dmid n}mu(d)) 单位元等于莫比乌斯函数和不变函数的卷积
- (d=1*1 Leftrightarrow d(n)=sum_{dmid n}1*1) 约数个数函数等于不变函数与不变函数作卷积
- (sigma=d*1 Leftrightarrow sigma=sum_{dmid n}d) 约数和函数等于约数个数函数和不变函数作卷积
- (phi=id*mu Leftrightarrow phi(n)=sum_{dmid n}dmu(n/d) Leftrightarrow frac{phi(n)}{n}=sum_{dmid n}frac{mu(d)}{d})
- (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))是两个数论函数,如果有
对于(g(n))有反演公式
证明
- 暴力证明
将反演公式右边的(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)$$
- 卷积证明
(f=g*1,mbox{那么}f*mu=g*1*mu mbox{,而常数函数和莫比乌斯函数互为逆元，卷积得单位元，因此}f*mu=g*1*mu=g)
点点杂项公式
约数相关
-
[d(ij)=sum_{xmid i}sum_{ymid j}[gcd(i,j)=1],洛谷p3327 ]