「数码」题解（基于代码分析）

题意简化

对于 $l$ 到 $r$ 之间的每个数 $x$，列出 $x$ 的所有约数。
对每个约数，取其最高位数字（1-9）。
统计每个数字 1-9 出现的总次数。

$1 \le l \le r \le 10^9$。

核心思想：贡献转换

1. 问题转化

不是枚举每个 $x$ 再枚举其约数，而是考虑每个可能的约数 $d$ 对多少个数 $x$ 有贡献。

对于一个固定的 $d$，它是哪些 $x$ 的约数？

• $x$ 是 $d$ 的倍数
• $x$ 在 $[l, r]$ 范围内

所以 $d$ 的贡献次数 = $[l, r]$ 中 $d$ 的倍数的个数 = $\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l-1}{d} \rfloor$

2. 只关心最高位

我们只关心 $d$ 的最高位数字。
最高位为 $i$ 的 $d$ 形如：$i, i\times10, i\times10+1, \dots$

即所有最高位为 $i$ 的数。

代码算法解析

1. solve(a, b) 函数

计算：在 $1$ 到 $a$ 中，以数字 $b$ 开头的数，作为约数的总贡献次数。

ll solve(ll a, ll b) {
    ll res = 0, beg, end;
    for (ll i = 1; i <= a / b; i *= 10) {
        beg = b * i;            // 区间开头
        end = min(a, beg + i - 1); // 区间结尾
        
        for (int j = beg; j <= end; j = k + 1) {
            k = min(a / (a / j), end);
            res += (k - j + 1) * (a / j);
        }
    }
    return res;
}

解释：

• i 表示位数：$1, 10, 100, 1000, \dots$
• beg = b * i：最高位为 $b$ 的 $i$ 位数的最小值
  • $b=3, i=1$ → 3
  • $b=3, i=10$ → 30
  • $b=3, i=100$ → 300
• end = min(a, beg + i - 1)：该位数的最大值
  • 比如 300-399（如果 $a$ 足够大）

这样枚举了所有最高位为 $b$ 的数。

2. 数论分块优化

对于区间 $[beg, end]$，直接枚举每个 $j$ 计算 $\lfloor \frac{a}{j} \rfloor$ 会超时。

使用数论分块：

• $\lfloor \frac{a}{j} \rfloor$ 的值在 $j$ 的一个区间内不变
• 对于 $j \in [L, R]$，$\lfloor \frac{a}{j} \rfloor$ 相等
• 可以一次性计算这个区间的贡献：$(R-L+1) \times \lfloor \frac{a}{L} \rfloor$

代码中：

for (int j = beg; j <= end; j = k + 1) {
    k = min(a / (a / j), end);
    res += (k - j + 1) * (a / j);
}

• j 是区间起点
• k 是当前值 $\lfloor \frac{a}{j} \rfloor$ 能保持不变的区间终点
• min(a / (a / j), end) 确保不超过当前位数区间的上限

3. 最终计算

对于每个数字 $i=1..9$：

cout << solve(r, i) - solve(l-1, i) << endl;

• solve(r, i)：$1$ 到 $r$ 中，最高位为 $i$ 的约数的总贡献
• solve(l-1, i)：$1$ 到 $l-1$ 中的贡献
• 差值就是 $[l, r]$ 区间的贡献

算法步骤

1. 枚举最高位数字 $b=1..9$
2. 枚举位数 $i=1,10,100,\dots$ 直到 $b\times i > a$
3. 对于每个 $[beg, end]$ 区间：
   • 使用数论分块计算 $\sum_{j=beg}^{end} \lfloor \frac{a}{j} \rfloor$
4. 求区间差：$[l, r]$ 的答案 = $[1, r]$ 的答案 - $[1, l-1]$ 的答案

复杂度分析

• 对于每个 $b$，位数 $i$ 有 $O(\log_{10} a)$ 个
• 每个区间用数论分块计算，复杂度 $O(\sqrt{end-beg})$
• 总复杂度：$O(9 \times \log a \times \sqrt{a})$，可过 $a=10^9$

关键优化

1. 贡献转换

从“每个数的约数”转为“每个约数的倍数”，避免平方复杂度。

2. 按最高位分组

将约数按最高位分组，分别统计。

3. 数论分块

高效计算 $\sum \lfloor \frac{a}{j} \rfloor$，避免线性枚举。

样例解释

输入：1 4

约数列表：

• 1: {1} → 最高位1
• 2: {1,2} → 最高位1,2
• 3: {1,3} → 最高位1,3
• 4: {1,2,4} → 最高位1,2,4

统计：

• 1出现4次
• 2出现2次
• 3出现1次
• 4出现1次
• 5-9出现0次

输出：

4
2
1
1
0
0
0
0
0

代码特点

• 使用 long long 防止溢出
• 数论分块模板
• 简洁的区间枚举
• 差值计算避免重复