📝 题目大意

给定正整数 $K$，求所有满足 $A \times B \times C \leq K$ 的正整数有序三元组 $(A, B, C)$ 的个数。$(A, B, C)$ 的顺序不同视为不同的三元组。

💡 解题思路

1. 题目分析：

   • 数据范围 $K \leq 2 \times 10^5$，不算大，但 $O(K^3)$ 的纯暴力（$8 \times 10^{15}$）不可行。
   • 正整数的条件意味着 $A, B, C \geq 1$，且乘积单调递增，可以通过逐步限制上界来剪枝。
   • 有序三元组意味着 $(1,2,3)$ 和 $(3,1,2)$ 算不同的组，无需去重。

2. 算法推导： 从朴素想法出发：枚举 $A$、$B$、$C$，但每个变量的上界受前面已确定变量的约束。

   • 首先固定 $A$（代码中变量 i），$A$ 的取值范围是 $1 \leq A \leq K$。

   • 在 $A$ 确定后，$A \times B \leq K$ 必须成立，否则 $C$ 最小取 $1$ 也会超限。因此 $B$（代码中变量 j）的上界是 $\lfloor K / A \rfloor$，即 n / i。

   • 同理，$A$ 和 $B$ 都确定后，$C$（代码中变量 k）的上界是 $\lfloor K / (A \times B) \rfloor$，即 n / i / j。

   • 对于每一组有效的 $(A, B)$，$C$ 可以取 $1$ 到 $\lfloor K / (A \times B) \rfloor$ 之间的任意整数，故内层循环实际上是在累加合法 $C$ 的个数。等价于：

     $$\text{答案} = \sum_{A=1}^{K} \sum_{B=1}^{\lfloor K/A \rfloor} \left\lfloor \frac{K}{A \times B} \right\rfloor$$

   这就是 std.cpp 中三重循环的直接含义：最内层 k 从 $1$ 到 n / i / j，每次 cnt++，本质上就是在做上述求和。

   为什么这个 $O(K \log^2 K)$ 的算法能过？因为上述求和式的值本身就是答案，而答案的增长速度约为 $O(K \log^2 K)$。当 $K = 2 \times 10^5$ 时，答案大约是 $1.5 \times 10^7 \sim 3 \times 10^7$ 量级，即三重循环的总迭代次数不超过几千万，C++ 在 2s 内完全可以通过。

3. 边界与细节：

   • $K = 1$ 时只有 $(1,1,1)$ 一组，答案为 $1$。代码中 i=1, j=1, k=1 各执行一次，cnt=1，正确。
   • 整数除法自动向下取整（C++ 中 int/int 截断），恰好对应 $\lfloor \cdot \rfloor$。
   • 溢出问题：$K \leq 2 \times 10^5$，答案最大约 $3 \times 10^7$，用 int（$2.1 \times 10^9$）完全足够，无需 long long。

⏱️ 复杂度分析

• 时间复杂度：三重循环的总迭代次数等于答案本身，即

  $$\sum_{A=1}^{K} \sum_{B=1}^{\lfloor K/A \rfloor} \left\lfloor \frac{K}{A \times B} \right\rfloor \sim O(K \log^2 K)$$

  当 $K = 2 \times 10^5$ 时约 $2 \times 10^7$ 次运算，可在时限内完成。

• 空间复杂度：仅使用几个整型变量（n, cnt, i, j, k），$O(1)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, cnt = 0;          // n = K, cnt 存储答案
    cin >> n;
    // 枚举 A (i), B (j), C (k)
    for(int i = 1; i <= n; i++)               // A 从 1 到 K
        for(int j = 1; j <= n / i; j++)       // B 从 1 到 floor(K/A)
            for(int k = 1; k <= n / i / j; k++) // C 从 1 到 floor(K/(A*B))
                cnt++;                         // 每个合法的 C 使答案 +1
    cout << cnt;
    return 0;
}