莫比乌斯反演学习笔记

• $整除分块$整除分块

$Q:$Q: 请以 $O\left(\sqrt{N}\right)$O(N ​) 的时间复杂度求解下式 $\downarrow$↓ $\sum _{i=1}^N\lfloor \frac{N}{i}\rfloor$i=1∑N​⌊iN​⌋

$A:$A: $\lfloor \frac{N}{i}\rfloor$⌊iN​⌋ 这个数列是 呈块状连续分布 的, 设某个块的 左端点 为 $l$l, 则这个块的 右端点 为 $\frac{N}{N/l}$N/lN​ (向下取整略) ,
于是该块的和为 $(r-l+1)\ast \lfloor \frac{N}{l}\rfloor$(r−l+1)∗⌊lN​⌋,

代码很简短:

for(reg int l = 1, r; l <= N; l = r+1){
		r = N/(N/l);
   		tmp += (r-l+1)*(N/l);
}

• $莫比乌斯函数$莫比乌斯函数

$定义:$定义:

设 $n=p_1^{k_1}\ast p_2^{k_2}......p_m^{k_m}$n=p1k1​​∗p2k2​​......pmkm​​

$\mu \left(n\right)=\{\begin{array}{c}1n=1\\ (-1{)}^m{\prod }_{i=1}^m{k}_i=1\\ 0else\end{array}$μ(n)=⎩⎪⎨⎪⎧​1               n=1(−1)m      ∏i=1m​ki​=10                else​

可以看出有 $单个质因子的幂数超过1$单个质因子的幂数超过1 的数字 莫比乌斯函数 值为 $0$0 .

$性质:$性质:

$性质1:$性质1: 莫比乌斯函数是 积性函数 :

$\mu (a\ast b)=\mu \left(a\right)\ast \mu \left(b\right)gcd(a,b)=1$μ(a∗b)=μ(a)∗μ(b)       gcd(a,b)=1

根据这个性质, 可以 $O\left(N\right)$O(N) 进行 线性筛,

• 若当前数字 $i$i 为质数, $\mu \left(i\right)=-1$μ(i)=−1,

• 若 $i\%p_j==0$i%pj​ ==0, 说明 $i\ast p_j$i∗pj​ 已经含有幂数大于 $1$1的质因子, 所以 $\mu (i\ast p_j)=0$μ(i∗pj​)=0,

• 否则说明 $i$i 的质因子与 $p_j$pj​ 共同构成 $i\ast p_j$i∗pj​的质因子,
  于是 $\mu (i\ast p_j)=\mu \left(p_j\right)\ast \mu \left(i\right)=-\mu \left(i\right)$μ(i∗pj​)=μ(pj​)∗μ(i)=−μ(i),
  这个式子同时处理了 $\mu \left(i\right)=0$μ(i)=0的情况 .

void sieve(){
        mu[1] = 1, p_cnt = 0;
        for(reg int i = 2; i < maxn; i ++){
                if(!Used[i]) p[++ p_cnt] = i, mu[i] = -1;
                for(reg int j = 1; j <= p_cnt && i*p[j] < maxn; j ++){
                        Used[i*p[j]] = 1;
                        if(i%p[j] == 0){ mu[i*p[j]] = 0; break ; }
                        else mu[i*p[j]] = -mu[i];
                }
        }
}

$性质2:$性质2:
$\sum _{d\mid N}\mu \left(d\right)=[N==1]$d∣N∑​μ(d)=[N==1]

证明:

• $N=1$N=1 时, $\mu \left(1\right)=1$μ(1)=1.

• $N!=1$N!=1 时,
  $N=p_1^{k_1}\ast p_2^{k_2}......p_m^{k_m}$N=p1k1​​∗p2k2​​......pmkm​​, $d=p_1^{q_1}\ast p_2^{q_2}......p_m^{q_m}$d=p1q1​​∗p2q2​​......pmqm​​,
  由于 质因子幂 大于 $1$1 的 $\mu$μ 值为 $0$0, 所以只需考虑 幂 为 $0,1$0,1 的质因子项,
  $\sum _{d\mid N}\mu \left(d\right)=\sum _{i=0}^m\left(\begin{array}{c}m\\ i\end{array}\right)\ast (-1{)}^i$d∣N∑​μ(d)=i=0∑m​(mi​)∗(−1)i
  因为有 二项式定理, 所以
  $原式=\sum _{i=0}^m\left(\begin{array}{c}m\\ i\end{array}\right)\ast (-1{)}^i\ast 1^{m-i}=(1-1{)}^m=0$原式=i=0∑m​(mi​)∗(−1)i∗1m−i =(1−1)m =0

证毕.

$二项式定理:$二项式定理: $(x+y{)}^n=\sum _{k=0}^n\left(\begin{array}{c}m\\ i\end{array}\right)x^{n-k}{y}^n$(x+y)n=k=0∑n​(mi​)xn−kyn

• $莫比乌斯反演$莫比乌斯反演

若 $f\left(n\right),g\left(n\right)$f(n),g(n) 为数论函数, 且
$f\left(N\right)=\sum _{d\mid N}g\left(d\right)$f(N)=d∣N∑​g(d)

则 莫比乌斯反演 为:
$g\left(d\right)=\sum _{d\mid N}\mu \left(\frac{N}{d}\right)f\left(d\right)或者\sum _{d\mid N}\mu \left(d\right)f\left(\frac{N}{d}\right)$g(d)=d∣N∑​μ(dN​)f(d)  或者  d∣N∑​μ(d)f(dN​)

证明:

$\sum _{d\mid N}\mu \left(d\right)f\left(\frac{N}{d}\right)=\sum _{d\mid N}\mu \left(d\right)\sum _{i\mid \frac{N}{d}}g\left(i\right)=\sum _{i\mid N}g\left(i\right)\sum _{k\mid \frac{N}{i}}\mu \left(k\right)=g\left(N\right)$d∣N∑​μ(d)f(dN​) =d∣N∑​μ(d)i∣dN​∑​g(i)  =i∣N∑​g(i)k∣iN​∑​μ(k) =g(N)

证毕.

说一下从第二步到怎么到第三步的,
先看第二步推导的含义: 枚举 $N$N 的约数 $d$d, 然后再去找与 $\mu \left(d\right)$μ(d) 相乘的 $g\left(i\right)$g(i),
分析 $d$d 与 $i$i 之间的关系, $i\ast t=\frac{N}{d}$i∗t=dN​ ( $t$t 为正整数), 进而得到 $d\ast t=\frac{N}{i}$d∗t=iN​, 即 $d\mid \frac{N}{i}$d∣iN​ ,
于是枚举 $i$i, 再枚举 $\frac{N}{i}$iN​ 的约数进行计算, 即第三步

• $莫比乌斯反演的变形$莫比乌斯反演的变形

若 $F\left(x\right)=\sum _{d=1}^{\lfloor \frac{N}{x}\rfloor }g\left(dx\right)$F(x)=d=1∑⌊xN​⌋​g(dx)

则 $g\left(x\right)=\sum _{d=1}^{\lfloor \frac{N}{x}\rfloor }F\left(dx\right)\mu \left(d\right)$g(x)=d=1∑⌊xN​⌋​F(dx)μ(d)

$证明:$证明:

$\sum _{d=1}^{\lfloor \frac{N}{x}\rfloor }F\left(dx\right)\mu \left(d\right)=\sum _{d=1}^{\lfloor \frac{N}{x}\rfloor }\mu \left(d\right)\sum _{i=1}^{\lfloor \frac{N}{dx}\rfloor }g(i\ast dx)$d=1∑⌊xN​⌋​F(dx)μ(d)=d=1∑⌊xN​⌋​μ(d)i=1∑⌊dxN​⌋​g(i∗dx)

设 $i\ast d=t(t\in [1,\lfloor \frac{N}{x}\rfloor \left]\right)$i∗d=t  (t∈[1,⌊xN​⌋]), 则 $d=t/i$d=t/i, 即 $d\mid t$d∣t.
即与 $F\left(tx\right)$F(tx) 进行运算的是 $\mu \left(t/i\right)$μ(t/i) .
于是枚举 $t$t, 得到 $\downarrow$↓

$原式=\sum _{t=1}^{\lfloor \frac{N}{x}\rfloor }g\left(tx\right)\sum _{d\mid t}\mu \left(d\right)=g\left(x\right)$原式=t=1∑⌊xN​⌋​g(tx)d∣t∑​μ(d)=g(x)
证毕.

• $莫比乌斯反演的应用$莫比乌斯反演的应用

$求解gcd(i,j)=1的对数$求解gcd(i,j)=1的对数

$解法:$解法:

$\begin{array}{}\text{(1)}& \sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=1](n\&lt;m)\end{array}$i=1∑n​j=1∑m​[gcd(i,j)=1]          (n<m)(1)

前面提到莫比乌斯函数的 性质2: $\sum _{i\mid N}\mu \left(i\right)=[N==1]$i∣N∑​μ(i)=[N==1]

将 $N$N 换成 $gcd(i,j)$gcd(i,j) 得到 : $\sum _{i\mid gcd(i,j)}\mu \left(i\right)=\left[gcd\right(i,j)=1]$i∣gcd(i,j)∑​μ(i)=[gcd(i,j)=1]

再代入 $1$1 式: $\sum _{i=1}^n\sum _{j=1}^m\sum _{d\mid gcd(i,j)}\mu \left(d\right)$i=1∑n​j=1∑m​d∣gcd(i,j)∑​μ(d)

再将 $d$d 提出来 :

$\sum _{d=1}^n\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \mu \left(d\right)$d=1∑n​⌊dn​⌋⌊dm​⌋μ(d)

$求解gcd(i,j)=k的对数$求解gcd(i,j)=k的对数

$解法1:$解法1:

将上方式子 $n,m$n,m 换为 $\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{m}{k}\rfloor$⌊kn​⌋,⌊km​⌋ 即可.

$解法2:$解法2:

前面提到莫比乌斯反演的 变形:

若 $F\left(x\right)={\sum }_{d=1}^{\frac{N}{x}}g\left(dx\right)$F(x)=∑d=1xN​​g(dx), 则 $g\left(x\right)={\sum }_{d=1}^{\frac{N}{x}}F\left(dx\right)\mu \left(d\right)$g(x)=∑d=1xN​​F(dx)μ(d),

于是设 $f\left(k\right)$f(k) 为 $gcd(i,j)=k$gcd(i,j)=k 的对数, $g\left(k\right)$g(k) 为 $k\mid gcd(i,j)$k∣gcd(i,j) 的对数, 显然有
$g\left(k\right)=\sum _{i=1}^{\lfloor \frac{N}{k}\rfloor }f(i\ast k)=\lfloor \frac{n}{k}\rfloor \lfloor \frac{m}{k}\rfloor$g(k)=i=1∑⌊kN​⌋​f(i∗k)=⌊kn​⌋⌊km​⌋
于是参照 莫比乌斯反演的变形. 得到
$f\left(k\right)=\sum _{x=1}^{\lfloor \frac{N}{k}\rfloor }g\left(kx\right)\mu \left(x\right)=\sum _{x=1}^{\lfloor \frac{N}{k}\rfloor }\lfloor \frac{n}{kx}\rfloor \lfloor \frac{m}{kx}\rfloor \mu \left(x\right)$f(k)=x=1∑⌊kN​⌋​g(kx)μ(x)=x=1∑⌊kN​⌋​⌊kxn​⌋⌊kxm​⌋μ(x)

$再提整除分块:$再提整除分块:

将 $\lfloor \frac{n}{kx}\rfloor \lfloor \frac{m}{kx}\rfloor$⌊kxn​⌋⌊kxm​⌋ 整除分块时, 要保证块内 $\lfloor \frac{n}{kx}\rfloor \lfloor \frac{m}{kx}\rfloor$⌊kxn​⌋⌊kxm​⌋ 相同, 每次可能就需要一个指针 “委曲求全”,
具体的说:
一个指针同时处理 $n,m$n,m 的块, 从起点 $1$1出发, 则下一步需要走到 $r=min\left(n/\right(n/l),m/(m/l\left)\right)$r=min(n/(n/l),m/(m/l)).

$求解gcd(i,j)的幂$求解gcd(i,j)的幂

$\sum _{i=1}^N\sum _{j=1}^{M}gcd(i,j{)}^k$i=1∑N​j=1∑M​gcd(i,j)k

$解法:$解法:

待填坑…