莫比乌斯反演

莫反入门

求 $\sum_{i =1}^{n}{(i, n)}$ n, q 均为5e4范围

这样的话时间复杂度为$\theta(q\sqrt {n})$

一开始可以考虑枚举对于值为$d$的$gcd(i,j)$有多少对,就可以把$f(d)$单独拿出来 后面的当成系数看。

考虑$gcd(i,j)$为d的有多少对的时候 , 可以想到每$d$个数里至多只有一个含有$d$这个因子,于是可以考虑把上界和判断值

都除以$d$, 然后就变成了求互质的$i,j$对数。

判断一个数是不是$1$这个玩意可以莫比乌斯反演一发 , 现在出来一个新的系数$e$,

哎咋看着越来越……麻烦了啊….. 等等….

这个时候可以发现 实际上就是在统计$\mu(e)$的和 这个时候我们再来考虑统计每个$\mu(e)$的系数, 因为在原来的位置中$e$是

作为因子出现 这个时候统计$\mu(e)$的系数实际上就是在统计合法的倍数对数于是就有$ K = n/de * m / de$ (下取整)

这个时候发现 K 的取值实际上是只受$d e$这两个东西影响的 所以我们考虑枚举$T = de$ 也就是考虑枚举$K$的系数 ,

后面枚举$T$的因子$d$实际上就是考虑$f(d)\mu(\frac{T}{d})$ 两者乘积对于K的贡献。也就是对于每个数$d$有以上贡献。

后面那个东西可以

1
for (int i = 1; i <= n; i++) for (int j = 1; j * i <= n; j++) g[i * j] += f[i] * mu[j];

复杂度是个调和级数。 每次回答可以数论分块, 就是求 $K$取值相同的一块左右边界。

1
2
for (int l = 1, r; l <= n; l = r + 1) 
r = min (n / (n / l), m / (m / l)) ans += (S(r) - S(l - 1)) * K;

$S(T)$是$g$的前缀和。 这个玩意可以做到$\sqrt{n}$回答一次询问。

对于因子枚举那部分 , 因为是求和 所以有对称性 , 意思就是说可以把$f(d)$换成$f(\frac{T}{d})$ 当然其他的也要换一下。

很多时候对于$g$这种函数可以线性筛 实在不行暴力加一下, 慢不到哪里去的。 还有一些时候需要杜教筛。

例题

咕咕咕

基本上套Eg2就完事… 自己去搜搜8……