自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:56:05，当前版本为作者最后更新于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);
        }
    }
}