P3455 题解
__vector__
·
·
题解
首先假设 a \le b。
求 \sum\limits_{x \in [1,a]}\sum\limits_{y \in [1,b]} [(x,y)=d]。
转化为： \sum\limits_{x=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{y=1}^{\lfloor \frac{b}{d}\rfloor}[(x,y)=1]
$= \sum\limits_{k=1}^{\lfloor \frac{a}{d}\rfloor}\mu(k) \lfloor \frac{a}{dk}\rfloor\lfloor\frac{b}{dk}\rfloor$。
整除分块。