结合律 $(f \times g ) \times h= f \times (g \times h)$。
交换律 $f \times g = g \times f$。
加法-狄利克雷卷积分配律 $f \times (g+h) = f\times g + f \times h$。
单位元 单位函数$\epsilon$，使得$f= \epsilon \times f =f \times \epsilon$。

单位函数的取值：$n=1$时$\epsilon(n)=1$，$n$取其他值时$\epsilon(n)=0$。
逆元 对于任意数论函数$f$，如果$f(1) \not = 0$，则存在唯一的逆函数$f^{-1}$，使得 $f \times f^{-1} = \epsilon$：

对于$n=1$，有：${f^{-1}(1)={\frac {1}{f(1)}}}$

对于$n>1$，有：$ {f^{-1}(n)={\frac {-1}{f(1)}}\displaystyle \sum _{d|n,n\neq d}f({\frac {n}{d}})f^{-1}(d)}$

特殊函数的奆积

由:$\sum_{d|n}\varphi(d)=n$再结合狄利克雷卷积的定义:

$\varphi*1=n$

根据Mobius反演的式子:

$F(n)=\sum_{d|n}f(d)$

写成卷积的形式就是:

$F = f*1$

事实上我们甚至可以用狄利克雷卷积的运算法则来证明莫比乌斯反演的正确性

$\huge{ \because \mu * 1=\epsilon \\\\ \therefore f*1=F*\mu*1 \\\\\therefore f=F *\mu}$

更有意思的是我们几乎可以不费吹灰之力，利用狄利克雷卷积运算的交换律,由:

$\huge f=F*\mu=\mu*F$ $\huge=>f(n)=\sum_{d|n}\mu(\frac{n}{d})F(d) = \sum_{d|n}\mu(d)F(\frac{n}{d})$

这么快就证完了,,,珂怕.

数论积性函数线性筛法

由积性函数的定义,大部分的数论函数如$\mu(x),\varphi(x)$都能在$Euler$线性筛中以$O(n)$的时间得到.

交出板子

inline void init(void)
{
	//phi[i]为欧拉函数,u[i]为莫比乌斯函数,f[i]为约数个数函数,g[i]为最高质因数的次方数 
	phi[1] = u[1] = f[1] = 1;
	for (int i = 2; i < maxn; i++)
	{
		if(!vis[i])
		{
			prime[++cnt] = i;
			u[i] = -1;
			f[i] = 2;
			g[i] = 1;
			phi[i] = i-1;
		}
		for(int j = 1;j <= cnt&& i*prime[j] <=maxn; j++)
		{
            vis[i*prime[j]]=true;
            if(i%prime[j]== 0)
			{
                u[i*prime[j]]=0;
                g[i*prime[j]]=g[i]+1;
                f[i*prime[j]]=f[i]/(g[i]+1)*(g[i]+2);
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            u[i*prime[j]]=-u[i];
            g[i*prime[j]]=1;
            f[i*prime[j]]=f[i]*2;
            phi[i*prime[j]] = phi[i] * (prime[j]-1);
        }
	}
}

这个板子应该够用了不然我就吃~~ckr~~

Mobius反演公式

$\huge{ \sum_{x|n}\mu(x)=[n=1]\\\\ \sum_{x|i}f(\frac{i}{x})=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}f(i)\\\\ \varphi(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})=\sum_{d|n}\frac{\mu(d)n}{d}\\\\ \sum_{d|n}\varphi(d)=n\\\\ }$

复杂的单题写题解吧.