G. D-函数 – 详细题解

问题描述

定义 $D(n)$ 为整数 $n$ 的十进制各位数字之和。给定 $l, r, k$，求满足 $10^{l} \le n < 10^{r}$ 且 $D(k \cdot n) = k \cdot D(n)$ 的整数 $n$ 的个数，答案对 $10^{9}+7$ 取模。

关键观察

考虑一个正整数 $n$ 的十进制表示 $n = \overline{d_{m-1} d_{m-2} \dots d_0}$（$d_{m-1} \neq 0$）。乘以 $k$ 后，数字和 $D(k \cdot n)$ 与 $k \cdot D(n)$ 的关系取决于乘法过程中是否发生进位。如果 $k$ 乘以每一位数字的结果都小于 $10$（即 $k \cdot d_i < 10$），则乘法不会产生进位，此时 $k \cdot n$ 的各位数字恰好就是 $k \cdot d_i$，因此数字和满足 $D(k \cdot n) = k \cdot D(n)$。反之，若有任何一位 $d_i$ 使得 $k \cdot d_i \ge 10$，则进位会破坏这种线性关系，等式一般不成立。

因此，条件 $D(k \cdot n) = k \cdot D(n)$ 等价于：$n$ 的每一位数字 $d$ 都满足 $k \cdot d < 10$，即 $d \le \lfloor \frac{9}{k} \rfloor$。

记 $t = \lfloor \frac{9}{k} \rfloor$。则允许的数字集合为 $\{0, 1, 2, \dots, t\}$，但首位（最高位）不能为 $0$。

特殊情况

• 当 $k \ge 10$ 时，$t = 0$，允许的数字只有 $0$，但首位不能为 $0$，因此不存在满足条件的正整数 $n$，答案为 $0$。
• 当 $k = 1$ 时，$t = 9$，所有数字 $0$ 到 $9$ 均允许，故任何 $n$ 都满足条件。
• 当 $1 < k < 10$ 时，$t$ 为 $1$ 到 $9$ 之间的某个正整数。

计数公式

$n$ 的取值范围是 $10^{l} \le n < 10^{r}$，即 $n$ 的十进制位数 $len$ 满足 $l+1 \le len \le r$（因为 $10^{len-1} \le n < 10^{len}$）。

对于固定的位数 $len$：

• 最高位可取 $1, 2, \dots, t$，共 $t$ 种选择。
• 其余 $len-1$ 位每位可取 $0, 1, \dots, t$，共 $t+1$ 种选择。

因此，位数为 $len$ 的符合条件的数共有 $t \cdot (t+1)^{len-1}$ 个。

将所有位数求和：

$$\begin{aligned} \text{总数} &= \sum_{len = l+1}^{r} t \cdot (t+1)^{len-1} \\ &= t \cdot \sum_{j=l}^{r-1} (t+1)^{j} \quad (\text{令 } j = len-1) \\ &= t \cdot \frac{(t+1)^l\bigl((t+1)^{r-l} - 1\bigr)}{(t+1)-1} \\ &= (t+1)^l \bigl((t+1)^{r-l} - 1\bigr) \\ &= (t+1)^r - (t+1)^l. \end{aligned} $$

因此，最终答案为：

$$\text{ans} = (t+1)^r - (t+1)^l, \qquad \text{其中 } t = \left\lfloor \frac{9}{k} \right\rfloor. $$

当 $k \ge 10$ 时，$t=0$，公式给出 $1^r - 1^l = 0$，与直接判断一致。

模运算与快速幂

由于 $l, r$ 最大可到 $10^9$，指数极大，必须使用快速幂计算 $(t+1)^l \bmod M$ 和 $(t+1)^r \bmod M$，其中 $M = 10^9+7$。注意答案须为正数，因此计算后取模并调整：

$$\text{ans} = \bigl( \text{pow}(t+1, r) - \text{pow}(t+1, l) + M \bigr) \bmod M. $$

时间复杂度

每个测试用例 $O(\log r)$，总复杂度 $O(t \log r)$，$t \le 10^4$，完全可行。

示例验证

• 样例1：$l=0, r=1, k=4$ → $t=\lfloor9/4\rfloor=2$，$t+1=3$，$3^1-3^0=3-1=2$。正确。
• 样例2：$l=0, r=2, k=7$ → $t=1$，$2^2-2^0=4-1=3$。正确。
• 样例3：$l=1, r=2, k=1$ → $t=9$，$10^2-10^1=100-10=90$。正确。
• 样例4：$l=1, r=2, k=3$ → $t=3$，$4^2-4^1=16-4=12$。正确。

总结

本题的核心在于发现 $D(kn)=kD(n)$ 等价于 $k$ 乘以 $n$ 的每一位均不产生进位。由此将问题转化为数位计数，并利用等比数列求和公式得到简洁的闭式解，最后用快速幂计算。