Luogu 2398 – GCD SUM

题目链接:Luogu 2398

套路推公式:

$$ \begin{aligned} & \sum_{i = 1}^{n} \sum_{j = 1}^{n} {\rm gcd}(i, j) \\ = & \sum_{d = 1}^{n} d \sum_{i = 1}^{n} \sum_{j = 1}^{n} [{\rm gcd}(i, j) = d] \\ = & \sum_{d = 1}^{n} d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor } \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} [{\rm gcd}(i, j) = 1] \\ = & \sum_{d = 1}^{n} d \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor } \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{t|i, t|j} \mu(t) \\ = &\sum_{d = 1}^{n} d  \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \lfloor \frac{n}{td} \rfloor ^ 2  \\ = & \sum_{d = 1}^{n} d \cdot f(\lfloor \frac{n}{d} \rfloor) \end{aligned} $$

其中

$$f(u) = \sum_{ i = 1}^{u} \mu(i) \lfloor \frac{u}{i} \rfloor ^ 2$$

因为这一题$n \leq 10^5$,$O(\sqrt{n} \times \sqrt{n})$可以过,所以化到这一步就可以做了。

实际上这一题还可以继续化简,令$td = k$:

$$ \begin{aligned} &\sum_{d = 1}^{n} d  \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \lfloor \frac{n}{td} \rfloor ^ 2  \\ = & \sum_{d = 1}^{n} d \sum_{k = 1} ^ {n} \mu (\frac{k}{d}) \lfloor \frac{n}{k} \rfloor ^ 2 \\ = & \sum_{k = 1}^{n} \lfloor \frac{n}{k} \rfloor ^ 2 \sum_{d | k} ^ {1 \leq d \leq n} d \cdot \mu(\frac{k}{d}) \\ =& \sum_{k = 1}^{n} \lfloor \frac{n}{k} \rfloor ^ 2 \varphi(k)  \end{aligned} $$

其中最后一步使用了一个常用关系$\mu * n = \varphi$,这样直接整除分块可以在$O(\sqrt{n})$的时间内求到答案。

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] Luogu 2398 – GCD SUM […]