2018-07-13 21:51:44

$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$

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

$$=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$

$$=\sum_{k=1}^{n}k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)$$

$$=\sum_{k=1}^{n}k\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*\lfloor\frac{n}{kd}\rfloor*\lfloor\frac{m}{kd}\rfloor$$

$$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{k|T}k*\mu(\frac{T}{k})$$

$$\sum_{k|T}k*\mu(\frac{T}{k})$$

$$=(id*\mu)(T)\ \ \ \ id(x)=x$$

$$\sum_{x|n}\varphi(x)=n=id(n)$$

$$=((1*\mu)*\varphi)(T)$$

$$=(e*\varphi)(T)$$

$$=\varphi(T)$$

$$\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor\sum_{k|T}k*\mu(\frac{T}{k})$$

$$=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor*\lfloor\frac{m}{T}\rfloor*\varphi(T)$$

## 其实，上面的做法，都是吃多了的做法

$$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\varphi(d)$$

$$=\sum_{d=1}^{n}\varphi(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor$$

• star
首页