# [UVA11426]GCD - Extreme (II) （莫比乌斯反演，数论分块）

### Description

Given the value of N, you will have to find the value of G. The definition of G is given below:

Here GCD(i,j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

UVA

## 解决思路

$Ans=\sum_{i=1}^{N} \sum_{j=1}^{N} gcd(i,j)$

$Ans=\sum_{d}^{N} d * \sum_{i}^{N} \sum_{j}^{N} [gcd(i,j)==d]=\sum_{d}^{N} d * \sum_{i}^{N/d} \sum_{j}^{N/d} [gcd(i,j)==1]$

$\sum_{i}^{N/d} \sum_{j}^{N/d} [gcd(i,j)==1]=\sum_{i}^{N/d} \mu(i) *\lfloor \frac{\lfloor \frac{N}{d} \rfloor }{i} \rfloor * \lfloor \frac{\lfloor \frac{N}{d} \rfloor }{i} \rfloor$

$Ans=\sum_{d=1}^{N} d* \sum_{i=1}^{n/d} \mu(i) * \lfloor \frac{\lfloor \frac{N}{d} \rfloor }{i} \rfloor * \lfloor \frac{\lfloor \frac{N}{d} \rfloor }{i} \rfloor$

HNCJ OIer 一枚