因为$gql$数论真的很差,,,所以决定给莫反开个专门的小结$QwQ$
然后因为我对这方面是真的很垃圾所以只会写下基础知识,经典例题和一些常见小套路.
依然不适合新手入门,也不适合入门进阶,只对$gql$本人比较友好$QwQ$
基础知识
首先莫反的本质,从我的理解上来说就是个容斥(,,,如果有锅并不是是我理解错了麻烦在评论里跟我港$kk$.
然后列几个基本式趴$QwQ$
- 若有$F(n)=sum_{d|n}f(d)$.则有$f(n)=sum_{d|n}mu(d)cdot F(frac{n}{d})$
- 若有$F(n)=sum_{n|d}f(d)$.则有$f(n)=sum_{n|d}mu(frac{d}{n})cdot F(d)$
- $sum_{d|n}mu(d)=[n==1]$
- $sum_{d|n}mu(frac{n}{d})cdot d=phi(n)$
事实上前两个是可以由后面被证出来的?但是我懒得证了,大概记下趴$kk$
经典例题
[X]$HDU1695$
[X]$luogu2522$
[X]$luogu2257$
[X]$luogu3455$
[X]$luogu4318$
[X]$luogu4450$
[X]$luogu2303$
[ ]$UVA11417$
[ ]$UVA11424$
[ ]$luogu3935$
[ ]$luogu2568$
[ ]$luogu1447$
[ ]$luogu1829$
[X]$luogu3327$
[ ]$luogu3312$
[ ]$luogu3768$
[ ]$luogu3704$
常见套路
只随便写点儿$kk$
求$gcd(i,j)=x$的个数.
$egin{align*}&=sum_{i=1}^nsum_{j=1}^n [gcd(i,j)==x]\&=sum_{i=1}^{frac{n}{x}}sum_{j=1}^{frac{n}{x}}[gcd(i,j)==1]\&=2cdotsum_{i=1}^{frac{n}{x}}sum_{j=1}^i[gcd(i,j)==1]-1\&=2cdotsum_{i=1}^{frac{n}{x}}phi(i)-1\end{align*}$
不对好像跑偏了,,,回来看莫比乌斯反演$kk$
回到第二步,设$f(x)=sum_{i=1}^{frac{n}{x}}sum_{j=1}^{frac{m}{x}}[gcd(i,j)==x],F(n)=sum_{n|d}f(d)$
发现$F(x)$的意义就,$x|gcd(i,j)$的数量,于是有$F(x)=frac{n}{x}cdot frac{m}{x}$
莫反就完事.
嗷然后有的情况下还要写个数论分块?我扩展再讲下$QwQ$
由莫反得$f(n)=sum_{n|d}mu(frac{d}{n})cdot F(d)=sum_{n|d}frac{n}{d}cdot frac{m}{d}cdot mu(frac{d}{n})$
然后数论分块就完事$QwQ$
求$gcd(i,j)in prime$的个数.
$egin{align*}&=sum_{i=1}^nsum_{j=1}^m [gcd(i,j)in prim]\&=sum_{i=1}^nsum_{j=1}^msum_{pin prim}[gcd(i,j)==p]\&=sum_{pin prim}sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==p]\&=sum_{pin prim}f(p)end{align*}$
发现这时候复杂度依然不行$QAQ$.于是继续拆式子变成,$sum_{pin prim}sum_{t=1}^{frac{min(m,n)}{p}}frac{n}{pcdot t}frac{m}{pcdot p} mu (t)$
设$T=pcdot t$.继续带入得
$egin{align*}&=sum_{pin prim}sum_{p|T}frac{n}{T}frac{m}{T} mu (frac{T}{p})\&=sum_{T=2}^{min(m,n)}frac{n}{T}frac{m}{T}cdot sum_{p|T}[pin prime]mu(frac{T}{p})end{align*}$
预处理一个$g(i)=sum_{p|i}[pin prim]cdot mu(frac{i}{p})$,于是原式化为$sum_{T=2}^{min(m,n)}frac{n}{T}frac{m}{T}cdot g(T)$
$over$
关于这个$g(i)$的预处理,就,枚举质数$p$,然后对$p$的每个倍数$T$加上$mu{T}{p}$就好
(,,,我$jio$得我差不多算重写了个题解$kk$
求约数个数和.
,,,不想写了直接看我博客趴$kk$
上面有点大,,,本来想写点儿小技巧的懒得写了,,,反正写多了自然而然就能总结出来了$QwQ$