算法笔记：数字集合与第 K 数问题

1. 核心定义与根本思想

问题描述：
定义一个数字是“有效”的（Valid），当它满足特定的数学公式或规则（如整除性质、由公式生成、特定的数位结构等）。
1. 计数问题：求区间 $[1, N]$ 中有多少个有效数字。
2. 第 K 数问题：求从小到大排列的第 $k$ 个有效数字。

根本思想 (The Root Idea)：
所有“求第 $k$ 个有效数字”的问题，本质上都是验证与计数问题。
我们将 “构造第 $k$ 个数” 的困难问题，转化为 “给定 $X$，求 $\le X$ 的有效数字个数” 的简单问题。

2. 通用解法框架

解法：二分答案 (Binary Search on Answer)
利用有效数字分布的单调性（数值越大，包含的有效数字越多），通过二分逼近答案。

代码模板：

// 目标：找到第 k 小的有效数字
long long l = 0, r = MAX_VAL; // 根据题目确定上下界
long long ans = -1;

while (l <= r) {
    long long mid = l + (r - l) / 2;
    if (count(mid) >= k) { // 核心：计算 <= mid 的有效数字个数
        ans = mid;
        r = mid - 1;       // 答案可能更小，往左找
    } else {
        l = mid + 1;       // 数不够，往右找
    }
}
// ans 即为所求

3. 三大考题类型与 `count(mid)` 实现策略

根据判断“有效性”的逻辑不同，count(mid) 函数有三种核心实现策略：

类型一：周期/模数类

特征：条件涉及整除 (x % a == 0) 或余数 (x % a == b)。
计数策略：LCM 周期法 + 容斥原理。
- 利用最小公倍数 $T = \text{LCM}(a, b, \dots)$ 将数轴划分为长度为 $T$ 的循环节。
- 预处理一个周期内的有效个数 $C$ 和前缀和数组 $P$。
公式：
$$Count(X) = \lfloor \frac{X}{T} \rfloor \times C + P[X \% T]$$
复杂度：$O(1)$ (预处理后)。

类型二：生成/组合类

特征：数字由变量运算生成，具有单调性。例如 $N \times N$ 乘法表、矩阵 $A_{ij} = i^2 + j^2$ 等。
计数策略：降维遍历 (Row-by-Row Counting)。
- 利用矩阵行或列的单调性，逐行计算符合条件的个数。
- 例如乘法表求 $\le X$ 的个数：$\sum_{i=1}^{n} \min(n, \lfloor \frac{X}{i} \rfloor)$。
复杂度：$O(N)$ 或 $O(N \log N)$。

类型三：数位结构类

特征：条件涉及数字的写法，如“不含数字4”、“回文数”。
计数策略：数位 DP (Digit DP) / 进制构造。
- 将 $X$ 拆解为十进制位，从高位到低位利用树形逻辑统计方案数。
- 状态通常包含：pos (当前位), limit (是否贴上界), state (是否已满足条件)。
复杂度：$O(\log_{10} X)$。

4. 总结对照表

考题类型	典型例题	核心难点	`count(X)` 实现关键词
周期类	第 K 个能被 3 整除但不能被 5 整除的数	找最小公倍数 (LCM)	数学公式、周期性、容斥
生成类	$N \times N$ 乘法表中第 K 小的数	利用单调性不重不漏	遍历、行统计、双指针
数位类	第 K 个不含 "4" 的整数	处理贴上界的限制	数位 DP、记忆化搜索