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。

題解：

數(shù)論 + 樹狀數(shù)組

先統(tǒng)計(jì) lcm(i,j,k)<i+j+k 的三元組個數(shù)。

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

根據(jù)最小公倍數(shù)的性質(zhì)可知，k 必然是 lcm(i,j,k) 的約數(shù) ，那么只有兩種可能：

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

lcm(i,j,k)=2×k 的情況，容易發(fā)現(xiàn)，只有 (3,4,6) 與 (6,10,15) 和它們的整數(shù)倍的情況能夠滿足。

再看另一種情況， i、j、k 的最小公倍數(shù)為 k，說明 i 和 j 都是 k 的約數(shù)，這是一個較強(qiáng)的性質(zhì)。

我們主要處理 lcm(i,j,k)=k 的情況 。

既然 i 和 j 都是 k 的約數(shù)，而且值域不大，所以可以先把 1～200000 中每個數(shù)除本身的約數(shù)處理出來。

為了使約數(shù)有序從而方便計(jì)算，這里求約數(shù)運(yùn)用了這種方法：

建立一個 vector，外層枚舉每個數(shù) i，內(nèi)層枚舉它的整數(shù)倍，即 2×i，3×i，...，一直到超出值域?yàn)橹梗?/p>

這些數(shù)它們都有共同的約數(shù) i，插入它們的約數(shù)數(shù)組中即可，不難發(fā)現(xiàn)現(xiàn)在每個數(shù)的約數(shù)組內(nèi)也是有序的。

枚舉 1～200000 中所有數(shù)，把每一個數(shù)都視作 k，此時對應(yīng)的 i 就是 k 的約數(shù)，?

i～k 中所有 k 的約數(shù)個數(shù) cnt 就是i相關(guān) 對答案的貢獻(xiàn)。

在樹狀數(shù)組的位置i，上傳cnt。

例如： 24的約數(shù)為：1，2，3，4，6，8，12

第4+1 個約數(shù)6，其相關(guān)貢獻(xiàn)數(shù)為 7-(4+1)=2

即為 6，8，24； 6，12，24

8，12，24也是答案，但是與6無關(guān)