前置知识:
狄利克雷卷积:
定义一个运算 (*),使得:
[(f*g)(n)=sum_{d|n}f(d)g(frac{n}{d})
]
一些常见的积性函数:
- 欧拉函数 (varphi(n))
- 莫比乌斯函数 (mu(n))
- 单位函数 (Id(n)=n)
- 不变函数 (1(n)=1)
- 幂函数 (Idk(n)=n^k)
- 狄利克雷卷积单位元 (epsilon=[n==1])
筛莫比乌斯函数:
首先介绍莫比乌斯函数的定义:
[mu=left{egin{matrix}1&quad(n=1)\(-1)^k&quad(n=P_1P_2cdots P_k)\0&(n={P_1}^{c_1}{P_2}^{c_2}cdots{P_k}^{c_k}|(sum_{i} c_i)>1)end{matrix}
ight.
]
一般就用欧拉筛去筛这个 (mu):
mu[1] = 1;
for (int i = 2; i <= N; i++)
{
if(!vis[i]) {pri[++cnt] = i, mu[i] = -1;}
for (int j = 1; j <= cnt && pri[j] * i <= N; j++)
{
vis[pri[j] * i] = 1;
if (i % pri[j] == 0)
{
mu[i * pri[j]] = 0;
break;
}
else
mu[i * pri[j]] = -mu[i];
}
}
反演:
主流的方法不太利于新手,新手一般可以用莫反 (mu*1=epsilon) 的性质化式子(虽然只是反演过程看上去不同,其实一样)。
至于这个 (mu*1=epsilon),我们可以证明它:
[mu*1=sum_{d|n}mu(d)=sum_{i=0}^{k}(-1)^iC_k^i
]
二项式定理展开是 ((x+y)^k=sum_{i=0}^{k}x^iy^{k-i}C_k^i),而我们化简得到的式子不就是 (x=-1,y=1) 时的情况吗?即:
[sum_{i=0}^{k}(-1)^iC_k^i=(-1+1)^k = 0^k =epsilon
]
在题目里我们要找到隐藏的 (epsilon),进而求解。
例题(从易到难):
【Luogu P3455】 [POI2007]ZAP-Queries
【Luogu P5518】[MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题