莫比乌斯反演常见模型
模型1：\(\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=t]\)
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=t]&=\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}[gcd(i,j)=1]\\ &=\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\sum_{d|gcd(i,j)}\mu(d)\\ &=\sum_{d=1}^{min(n,m)}\sum_{d|i}^{\lfloor\frac{n}{t}\rfloor}\sum_{d|j}^{\lfloor\frac{m}{t}\rfloor}\mu(d)\\ &=\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{td}\rfloor\lfloor\frac{m}{td}\rfloor\mu(d) \end{aligned} \]模型2：\(\sum_{i=1}^n\sum_{j=1}^mij[gcd(i,j)=t]\)
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^mij[gcd(i,j)=t]&= \sum_{d=1}^{min(n,m)}\mu(d)\sum_{d|i}^{\lfloor\frac{n}{t}\rfloor}\sum_{d|j}^{\lfloor\frac{m}{t}\rfloor}ij\\ &=\frac{\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{td}\rfloor\lfloor\frac{m}{td}\rfloor(\lfloor\frac{n}{td}\rfloor+1)(\lfloor\frac{m}{td}\rfloor+1)}{4} \end{aligned} \]至于推导的话就是等差数列求和而已
模型3：\(\sum_{i=1}^n\sum_{j=1}^mf[gcd(i,j)=t]\)
这个的推导就总结向上面一样照葫芦画瓢推就行了
答案如下：
\[\sum_{u=1}^{min(n,m)}\lfloor\frac{n}{u}\rfloor\lfloor\frac{m}{u}\rfloor\sum_{d|u}f(d)\mu(\frac{u}{d}) \]注意所有的求和都要用到整除分块
标签：lfloor,frac,gcd,乌斯,sum,rfloor,反演,莫比,td From： https://www.cnblogs.com/Zhangrx-/p/17391543.html