[BZOJ 2820] YY的GCD
题意
求下式的值:
题解
反演真棒 $$
\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来然后倍数反演, 然后xjb倒腾求和号把下取整部分的枚举翻到最外层, 然后筛里层就星了
里层就是 $$
g(x)=\sum_{p | x}\mu\left(\frac x p\right)
