蒟蒻刚开始学莫比乌斯[懵比钨丝]反演x
开始反演之前先解释一下莫比乌斯函数的定义？
莫比乌斯函数$μ$ 定义如下
$μ(n)$=1{$n=1$}
$μ(n)$=${-1}^{k}${$n$=$p_1p_2p_3p_4....p_k$}
$μ(n)$=$0${$otherwise$}
文字定义就是 如果一个数字是一个没有平方因子的数字 那么它的莫比乌斯函数就是$(-1)^k$ $k$定义为因子个数
如果$n$是$1$ 函数值为$1$
其他情况 函数值为$0$
莫比乌斯函数的性质:
1、莫比乌斯函数是一个积性函数
$prove$
这个应该挺显然的...?
然后我们知道线性筛可以计算积性函数 于是我们就可以线性筛莫比乌斯函数
附上代码:
mu[1]=1; for (int i=2;i<=n;i++) { if (!IsPrime[i]){ Index++; Prime[Index]=i; mu[i]=-1; } for (int j=1;j<=Index&&i*Prime[j]<=n;j++) { IsPrime[i*Prime[j]]=true; if (i%Prime[j]==0) break; else mu[i*Prime[j]]=-mu[i]; } }
2、$sum_{d|n}μ(d) =[n==1]$
$prove$
只考虑$μ(d)==1$的情况
设$n=p_1p_2p_3p_4...p_k$
$d$的质因子个数是$j$的方案数$C_{k}^{j}$
也就是说 $sum_{d|n}μ(d)$=$C_{k}^{0}-C_{k}^{1}+C_{k}^{2}...+(-1)^{m}C_{k}^{k}$
根据二项式定理 这东西等于$0$
开始反演？
莫比乌斯反演的公式是:
形式一:
$F(n)$=$sum_{d|n}f(d)$
则有$f(d)$=$sum_{d|n}μ(frac{n}{d})F(d)$=$sum_{d|n}F(frac{n}{d})μ(d)$
形式二:
$F(n)$=$sum_{n|d}f(d)$
则有$f(n)$=$sum_{n|d}μ(frac{d}{n})F(d)$
在很多时候我们能比较容易地求出$F(n)$ 但求不出$f(n)$的时候 就可以用这个东西了w
$prove$
我不会啊 咕咕咕
举个例子?
给定整数n和k 求在[1..n]之间有多少对$(i,j)$ 满足$gcd(i,j)==k$
做法一:
可以发现 题目是在求解形如$sum_{1<=i<=n}sum_{1<=j<=n}[gcd(i,j)==k]$
然后我们可以除一下
变成$sum_{1<=i<=frac{n}{k}}sum_{1<=j<=frac{n}{k}}[gcd(i,j)==1]$
根据莫比乌斯函数的性质2
变成$sum_{1<=i<=frac{n}{k}}sum_{1<=i<=frac{n}{k}}sum_{d|gcd(i,j)}μ(d)$
考虑把枚举因数变成枚举倍数 我们枚举d
则有:$sum_{d=1}^{n}μ(d)sum_{i=1}^{n}[d|i]sum_{j=1}^{n}[d|j]$
也就是说 后面两个式子统计的其实是$n$中有多少个数字是$d$的倍数
显然 答案是$frac{n}{d}$
所以 答案就变成了$sum_{d=1}^{n}μ(d)frac{n}{d}frac{n}{d}$
然后数论分块瞎搞一下就行了233
做法二:
既然要大力反演就要构造出合适的$F$和$f$
考虑怎么构造
答案式$f(x)$=$sum_{1<=i<=n}sum_{1<=j<=n}[gcd(i,j)==k]$
定义$F(d)$=$sum_{1<=i<=n}sum_{1<=j<=n}sum_{d}[d|gcd(i,j)]$
$F(d)$=$sum_{1<=i<=n}sum_{d|i}f(i)$
然后我们有了这个式子之后 就可以大力根据形式二反演了
$f(n)$=$sum_{n|d}F(d)μ(frac{d}{n})$
只要枚举到n就行了
$F(d)$=$sum_{1<=i<=n}sum_{1<=j<=n}sum_{d}[d|gcd(i,j)]$
其实就是在$n$的范围内 有多少对$gcd(i,j)$是$d$的倍数
就直接算因数
是$frac{n}{d}$
然后发现我们要求解$f(1)$
$f(1)$=$sum_{1|d}F(d)μ(frac{d}{1})$
即$f(1)$=$sum_{d}F(d)μ(d)$
代入 $f(1)$=$sum_{d}frac{n}{d}frac{n}{d}μ(d)$
然后得到了一样的答案233