数论函数
常见数论函数
- \(\epsilon(n)=[n=1]\)
- \(I(n)=1...\)
- \(id(n)=n\)
- \(id^k(n)=n^k\)
- \(\mu\)莫比乌斯函数
- \(\phi\)欧拉函数
- \(\tau\)约数个数
- \(\sigma\)约数和
欧拉函数
\(\phi(n)\)表示的是小于等于n和n互质的数的个数，是积性函数
\(\phi(p^k)=p^k-p^{k-1}\)
\(n=\sum_{d|n}\phi(d)\)
莫比乌斯函数
\[\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} \]\[\sum_{d\mid n}\mu(d)=\epsilon(n) \]常见关系
- \(\mu*I=\epsilon\)
- \(\phi*I=id\)
- \(\mu*id=\phi\)
- \(I*id=\sigma\)
- \(I*I=\tau\)
杜教筛常用
- \(f(n)=n^k\mu(n),f*id^k=\epsilon\)
- \(f(n)=n^k\phi(n),f*id^k=id^{k+1}\)
- \(f(n)=\sum_{d|n}d\mu(d),f*\phi=\epsilon\)
证明：
\[\begin{aligned} (f*\phi)(n)&=\sum_{i|n}\sum_{d|i}d\mu(d)\phi(\frac ni)\\ &=\sum_{d|n}d\mu(d)\sum_{i|\frac nd}\phi(i)\\ &=\sum_{d|n}d\mu(d)\frac nd\\ &=\sum_{d|n}\mu(d)\\ &=\epsilon(n) \end{aligned} \]tricks
1
已知 \(S\) 为积性函数，求
\[\sum_i^n\sum_j^nS(ij) \]我们考虑枚举一个 \(gcd(i,j)=g\)
\[\sum_g^n\sum_i^{\lfloor\frac ng\rfloor}\sum_j^{\lfloor\frac ng\rfloor}S(ijg^2)[\gcd(i,j)==1] \]我们令 \(H(i)=\frac{S(ig^2)}{S(g^2)}\) ，那么原式为
\[\sum_g^nS(g^2)\sum_i^{\lfloor\frac ng\rfloor}\sum_j^{\lfloor\frac ng\rfloor}h(ij)[\gcd(i,j)==1] \]可以证明 \(H\) 为积性函数，后面部分可以简单的求出
证明如下：
令 \(\gcd(a,b)=1,g^2=x_1x_2x_3\)，
使得 \(\gcd(a,x_2)=\gcd(a,x_3)=\gcd(a,x_1)=\gcd(a,x_2)=\gcd(x_1,x_2,x_3)=1\)
那么
\[\begin{aligned} H(a)H(b) &=\frac{S(ag^2)S(bg^2)}{S^2(g^2)} \\ &=\frac{S(ax_1x_2x_3)S(bx_1x_2x_3)}{S^2(g^2)}\\ &=\frac{S(ax_1)S(x_2)S(x_3)S(bx_3)S(x_1)S(x_2)}{S^2(g^2)}\\ &=\frac{S(ax_1)S(bx_3)S(x_2)}{S(g^2)}\\ &=\frac{S(abg^2)}{S(g^2)}\\ &=H(ab) \end{aligned} \]证毕
2
给定序列 \(A,B,C\)，求
\[\sum_{i=1}^n\sum_{j=1}^nA(i)B(j)C(gcd(i,j)) \]先枚举gcd
\[\sum_{g=1}C(g)\sum_{i=1}^{n/g}\sum_{j=1}^{n/g}A(ig)B(jb)[gcd(i,j)==1]\\ \sum_{g=1}C(g)\sum_{i=1}^{n/g}\sum_{j=1}^{n/g}A(ig)B(jb)\sum_{t|i,t|j}\mu(t)\\ \sum_{t=1}^n\sum_{g=1}^{n/t}C(g)\mu(t)\sum_{i=1}^{n/tg}\sum_{j=1}^{n/tg}A(ig)B(jb)\\ \] 标签：phi,frac,函数,数论,sum,mu,id,gcd From： https://www.cnblogs.com/zhy114514/p/18028187