由于一道题目用到了莫反，所以学了一下，赶紧隔了好几天才想起来记下来。
STO 忘忧老师是神！！！/bx/bx/bx
莫比乌斯反演
前置芝士：莫比乌斯函数：
\(\mu\) 为莫比乌斯函数，定义为:
\[设：\ n=\prod_{i=1}^{k}p_i^{c_i} \\ 则：\mu(n) =\begin{cases} 1 &n=1\\ 0 &\exist c_i>1\\ (-1)^k &\forall c_i=1\\ \end{cases} \]可以知道，这是个极性函数，所以求解可以用线性筛（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!ck[i]) p[++num]=i,mu[i]=-1;
for(int j=1;j<=num&&p[j]*i<=n;j++)
{
ck[p[j]*i]=1;
if(!(i%p[j])) break;
mu[p[j]*i]=-mu[i];
}
}
莫比乌斯反演：
结论：
\[[\ \gcd(i,j)=1] = \sum_{d|gcd(i,j)}\mu(d) \]转化应用：
求：\(\sum_{i=1}^n \sum_{j=1}^m [\ \gcd(i,j)=1]\)
解：
\[\begin{align*} \sum_{i=1}^n \sum_{j=1}^m [\ \gcd(i,j)=1] &= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|gcd(i,j)} \mu(d)\\ &= \sum_{d|i} \mu(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j]\\ &= \sum_{d|i}^{\min(n,m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \\ \end{align*}\]这样我们就可以 \(O(n)\) 求解了，如果用整除分块的话可以做到 \(O(\sqrt{n})\)，但是 \(\mu\) 的求解是 \(O(n)\) 的，如果要加快的话还要杜教筛等科技。
标签：gcd,乌斯,sum,mu,反演,莫比 From： https://www.cnblogs.com/Jack-YT/p/18311155