题解 P10239【[yLCPC2024] G. 系ぎて】

rui_er · 2024-03-09 18:47:46 · 题解

unintended solution。

暴力枚举三元组中最小的数是什么、次小的数是什么，容易计算出最大的数的方案数，乘系数即可得到有序的方案数。

时间复杂度 \displaystyle T(n)=O\left(\sum_{x=1}^{n^{\frac{1}{3}}}\left(\frac{n}{x}\right)^{\frac{1}{2}}\right)=O\left(n^{\frac{1}{2}}\int_0^{n^{\frac{1}{3}}}x^{-\frac{1}{2}}\text d x\right)=O\left(n^{\frac{2}{3}}\right)。

for(ll x = 1; x * x * x <= n; ++x) {
    for(ll y = x; x * y * y <= n; ++y) {
        if(x == y) {
            // y == z
            ++ans;
            // y != z
            ans += 3 * (n / (x * y) - (y + 1) + 1);
        }
        else {
            // y == z
            ans += 3;
            // y != z
            ans += 6 * (n / (x * y) - (y + 1) + 1);
        }
    }
}