DTOJ 2937. Sum of LCM

本文主要是介绍DTOJ 2937. Sum of LCM，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
对于 $A_1,A_2,\dots ,A_N$ ，求${\sum }_{i=1}^N{\sum }_{j=1}^N\mathrm{l}\mathrm{c}\mathrm{m}(A_i,A_j)$ 的值。

$\mathrm{l}\mathrm{c}\mathrm{m}(a,b)$ 表示 $a$ 和 $b$ 的最小公倍数
题解：
如果先考虑数$A_i$，再算$lcm$的贡献，则难以避免$O(N^2)$的枚举，故换一个角度，考虑枚举$gcd$，计算以这个数为$gcd$的每对数的贡献。而对于是两个数的$gcd$这样的条件也不好判断，故先退一步，将条件改为是两个数的公约数，于是，对于枚举的每一个$d$，记$s[d]$为${\sum }_{i=1}^N{A}_i/d\ast [d|A_i]$，则$d$作为公约数的贡献为$s[d{]}^2\ast d$，然后考虑计算作为真正$gcd$时的贡献，即减去所有它的倍数的答案*倍数大小。

这篇关于DTOJ 2937. Sum of LCM的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---