A - ABC

​比赛编号​：无

任务总览

题目描述

给定一个正整数 ​K​，找到所有满足条件的三元组 ​**(A, B, C)​，使得 ​A * B * C ≤ K**​。如果两个三元组仅在数字的顺序上不同，也视为不同的三元组。

输入格式

输入包含一个正整数 ​K​。

1 ≤ K ≤ 2 × 10⁵

输出格式

输出满足条件的三元组的数量。

输入输出示例

示例 1

输入：

2

输出：

4

解释： 符合条件的三元组为： (1, 1, 1)、(1, 1, 2)、(1, 2, 1)、(2, 1, 1)。

示例 2

输入：

10

输出：

53

示例 3

输入：

31415

输出：

1937281

时间复杂度分析

本题的核心操作是枚举 ​A, B, C​，并对每一种组合检查是否满足 ​A * B * C ≤ K​。为了提高效率，可以通过对 A 和 B 的枚举进行优化，减少不必要的计算。

由于最大 ​K = 2 × 10⁵​，因此我们可以预估最坏情况的时间复杂度为 ​O(K²)​，对于最大值的 ​K​，此解法足够高效。