UVA 11417 – GCD

题目链接:UVA – 11417

相似题目:Luogu 2398 GCD SUM 题解

题目要求

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

其实是意味着$(i, j)$和$(j,i)$只算一次。那么根据容斥原理,答案为:

$$ \frac{\sum_{i = 1}^{n} \sum_{j = 1}^{n} {\rm gcd}(i,j) – \sum_{d = 1}^{n} d [(d, d) = d]}{2} $$

根据相似题目 Luogu 2398 GCD SUM 题解 中的推导:

$$ \sum_{i = 1}^{n} \sum_{j = 1}^{n} {\rm gcd}(i,j) = \sum_{k = 1}^{n} \varphi(k) \lfloor \frac{n}{k} \rfloor ^ 2 $$

这样对于每次询问时间复杂度为$O(\sqrt{n})$。

 

说点什么

avatar
50
  Subscribe  
提醒