【BZOJ2005】【NOI2010】能量采集

显然这题要求

$$\sum_{i\in [1,n]}\sum_{j\in [1,m]}gcd(i,j)$$

手推了半天不会做，感觉很复杂的容斥

一看题解发现真**巧妙

令\(f[k]\)表示\(gcd(i,j)=k\)的\((i,j)\)对数

那么首先满足\(k|gcd(i,j)\)的\((i,j)\)对数为\(\left\lfloor\frac{n}{k}\right\rfloor\times\left\lfloor\frac{m}{k}\right\rfloor\)

再减去整数倍的就可以了

Update：学了莫比乌斯反演回来再把这题做一下（虽然还麻烦一些？）

令\(f(k)\)表示\(gcd(i,j)=k\)的\((i,j)\)对数，\(g(k)\)表示\(k|gcd(i,j)\)的\((i,j)\)对数

那么显然有\(g(k)=\sum_{k|d}f(d)=\left\lfloor\frac{n}{k}\right\rfloor\times\left\lfloor\frac{m}{k}\right\rfloor\)

用一下莫比乌斯反演\(f(k)=\sum_{k|d}\mu(\frac{d}{k})g(d)\)