目录

[BZOJ 2820] YY的GCD

目录
迁移提示
本文迁移自博客园, 原文链接

题意

求下式的值:

$$ \sum_{i=1}^n\sum_{j=1}^m \mathbb{P}(\gcd(i,j)) $$ 其中 $\mathbb{P}(x)$ 当 $x$ 为质数时为 $1$, 否则为 $0$.

题解

反演真棒 $$

\begin{aligned} f(x)&= \sum_i^N\sum_j^M[\gcd(i,j)=x] \
F(x)&= \sum_{x|m}f(m) \
&=\left \lfloor \frac N x \right \rfloor\left \lfloor \frac M x \right \rfloor \
\text{Ans}&=\sum_p f(p) \
&=\sum_p \sum_{p|m}F(m)\mu(\frac m p) \
&=\sum_p \sum_{p|m}\left \lfloor \frac N m \right \rfloor\left \lfloor \frac M m \right \rfloor \mu\left(\frac m p\right) \
&p|m\Rightarrow m=pd \
&=\sum_p \sum_{d=1}^{\left \lfloor \frac N p \right \rfloor}\left \lfloor \frac N {pd} \right \rfloor\left \lfloor \frac M {pd} \right \rfloor \mu(d) \
&\text{let} \ T = pd \Rightarrow d = \frac T p\
&=\sum_{T=1}^N \sum_{p|T} \left \lfloor \frac N {T} \right \rfloor\left \lfloor \frac M {T} \right \rfloor \mu \left(\frac T p \right)\
&=\sum_{T=1}^N \left \lfloor \frac N {T} \right \rfloor\left \lfloor \frac M {T} \right \rfloor \sum_{p|T} \mu \left(\frac T p \right) \end{aligned}

$$ ~~没有GCD就没有`mu`~~

搞出GCD来然后倍数反演, 然后xjb倒腾求和号把下取整部分的枚举翻到最外层, 然后筛里层就星了

里层就是 $$

g(x)=\sum_{p | x}\mu\left(\frac x p\right)

$$ 里层的话设当前基数为 $i$, 要乘上去的质数为 $p$, 要筛的值为 $t=pi$, 则当 $p \not \mid i$ 的时候会给这个和式增加一项 $\mu\left(\frac t p \right)$ 也就是 $\mu(i)$, 同时原来的求和项中所有的 $\mu$ 值都会因为新质因子的加入而被取反, 所以 $g(t)=\mu(i)-g(i)$. 而当 $p \mid i$ 的时候, 因为加入了平方因子, 那么所有的没有除去当前 $p$ 的 $\frac t {p'}$ 都会包含一个 $p^2$ 因子, 所以 $\mu$ 值为 $0$, 唯一还能对这个和式产生贡献的就只有 $\mu \left (\frac t p \right )$ 也就是 $\mu (i)$ 了. 于是这种情况下 $g(t)=\mu(i)$.

https://pic.rvalue.moe/2021/08/02/00f599846a7c0.jpg