AC代码

https://codeforces.com/contest/1712/submission/177510162

题意：

给定 l、r，求 l 到 r 之间有多少三元组 (i,j,k)，满足 lcm(i,j,k)≥i+j+k 且 i<j<k。

题解：

数论 + 树状数组

先统计 lcm(i,j,k)<i+j+k 的三元组个数。

由于 i<j<k，所以 i+j+k≤3k ，从而得出 lcm(i,j,k)<3×k。

根据最小公倍数的性质可知，k 必然是 lcm(i,j,k) 的约数 ，那么只有两种可能：

lcm(i,j,k)=k 或 lcm(i,j,k)=2×k 。

lcm(i,j,k)=2×k 的情况，容易发现，只有 (3,4,6) 与 (6,10,15) 和它们的整数倍的情况能够满足。

再看另一种情况， i、j、k 的最小公倍数为 k，说明 i 和 j 都是 k 的约数，这是一个较强的性质。

我们主要处理 lcm(i,j,k)=k 的情况 。

既然 i 和 j 都是 k 的约数，而且值域不大，所以可以先把 1∼200000 中每个数除本身的约数处理出来。

为了使约数有序从而方便计算，这里求约数运用了这种方法：

建立一个 vector，外层枚举每个数 i，内层枚举它的整数倍，即 2×i，3×i，...，一直到超出值域为止，

这些数它们都有共同的约数 i，插入它们的约数数组中即可，不难发现现在每个数的约数组内也是有序的。

枚举 1∼200000 中所有数，把每一个数都视作 k，此时对应的 i 就是 k 的约数， 

i∼k 中所有 k 的约数个数 cnt 就是i相关 对答案的贡献。

在树状数组的位置i，上传cnt。

例如： 24的约数为：1，2，3，4，6，8，12

第4+1 个约数6，其相关贡献数为 7-(4+1)=2

即为 6，8，24； 6，12，24

8，12，24也是答案，但是与6无关