2023.11.28 cf上的1900D
容斥原理
先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
本题思路
由本题数据不难看出暴力枚举肯定超时。
先对数组排序，再在其中找出gcd值为x以及x的倍数的所有三元组相加。
由容斥原理，在最后只需要从f(x)中减去f(2x)、f(3x)......，得到的结果就是gcd三元组中值为x的个数，再乘以x即为相应的贡献，贡献相加即为答案。
刷题：容斥原理 最大公约数gcd
发布时间 2023-11-28 11:15:59作者: modemingzi