区间计数

GitHub跳转原题关系图返回列表

由数根与模 9 同余把 V=x·D(x) 拆成九族等差数列,按 V mod 9 归并并做一次容斥,单次询问 O(1) 前缀相减。

OJ: roj

题目 ID: 1807

难度:普及+/提高-

标签:数学数论同余python

创建: 2026-10-08 04:27

更新: 2026-10-08 04:27

形式化题目

对正整数 nn,记 S(n)S(n) 为 nn 的各位数字之和,并按

D(n)={S(n),S(n)<10D(S(n)),S(n)⩾10D(n)=\begin{cases}S(n), & S(n)<10\\ D(S(n)), & S(n)\geqslant 10\end{cases}
递推定义数根 D(n)D(n)。若正整数 VV 可以写成
V=x⋅D(x)(x⩾1)V=x\cdot D(x)\qquad (x\geqslant 1)
则称 VV 是"小D喜欢的数"。

给出 TT 组询问,每组给一个合法区间 [L,R][L,R],求 [L,R][L,R] 内不同的"小D喜欢的数"的个数。 T⩽20T\leqslant 20,L,R⩽1018L,R\leqslant 10^{18},时限 1000 ms / 256 MB。

注意"不同的"是硬要求:同一个 VV 可以由两个不同的 xx 生成, 64=64⋅D(64)=64⋅164=64\cdot D(64)=64\cdot 1,也可以由 x=8 (D(8)=8)x=8\,(D(8)=8) 生成 8⋅8=648\cdot 8=64; 36=6⋅D(6)=6⋅636=6\cdot D(6)=6\cdot 6,也可以由 x=12 (D(12)=3)x=12\,(D(12)=3) 生成 12⋅3=3612\cdot 3=36。 所以枚举出的 VV 必须去重,不能按 xx 计数。

正解

思路

朴素做法。 枚举 x∈[1,R]x\in[1,R],算出 V=x⋅D(x)V=x\cdot D(x),若 V∈[L,R]V\in[L,R] 就记进集合,最后输出集合大小。 正确性显然,但 RR 可达 101810^{18},单次询问就是 101810^{18} 次循环,连样例之外的第二组数据都过不了。

换方向:枚举 VV 也不行。 对每个 V∈[L,R]V\in[L,R] 反查是否存在 xx 使 V=x⋅D(x)V=x\cdot D(x), 复杂度是区间长度 R−L+1R-L+1,同样可到 101810^{18};而且 VV 的十进制各位与 xx 的各位之间 被"整体数值相乘"搅在一起,做不了数位 DP 那样的按位转移。

突破口是数根的同余本质。 数根有两个等价刻画,这是全题的钥匙:

D(n)=1+(n−1) mod 9⟺n≡D(n)(mod9).D(n)=1+(n-1)\bmod 9 \qquad\Longleftrightarrow\qquad n\equiv D(n)\pmod 9 .

也就是说,一个正整数 nn 的数根是 kk(1⩽k⩽91\leqslant k\leqslant 9,余 00 记作 99)当且仅当 n≡k(mod9)n\equiv k\pmod 9。数根这个"反复求数位和"的操作,在计数里可以完全丢掉, 只留下一个模 99 的余数。

固定数根 kk,看 VV 长什么样。 若 D(x)=kD(x)=k,则 x=9m+k  (m⩾0)x=9m+k\;(m\geqslant 0),于是

V=x⋅D(x)=(9m+k)⋅k=9k m+k2.V=x\cdot D(x)=(9m+k)\cdot k=9k\,m+k^{2}.

也就是说,D(x)=kD(x)=k 能生成的 VV 恰好是首项 k2k^{2}、公差 9k9k 的等差数列:

数根 kk xx 的形式 生成的 VV 同余式
1 9m+19m+1 9m+19m+1 V≡1(mod9)V\equiv 1\pmod 9
2 9m+29m+2 18m+418m+4 V≡4(mod18)V\equiv 4\pmod{18}
3 9m+39m+3 27m+927m+9 V≡9(mod27)V\equiv 9\pmod{27}
4 9m+49m+4 36m+1636m+16 V≡16(mod36)V\equiv 16\pmod{36}
5 9m+59m+5 45m+2545m+25 V≡25(mod45)V\equiv 25\pmod{45}
6 9m+69m+6 54m+3654m+36 V≡36(mod54)V\equiv 36\pmod{54}
7 9m+79m+7 63m+4963m+49 V≡49(mod63)V\equiv 49\pmod{63}
8 9m+89m+8 72m+6472m+64 V≡64(mod72)V\equiv 64\pmod{72}
9 9m+99m+9 81m+8181m+81 81∣V81\mid V

九族各自是一个等差数列,"喜欢的数"就是这九个等差数列集合并起来。于是问题变成 “求并集中落在区间内的元素个数”,只剩两件事:族内计数(整除)与族间去重(容斥)。

关键观察:这九族按 V mod 9V\bmod 9 分成四组,同组内才有重叠。 因为 V=k2+9kmV=k^2+9km, 必有 V≡k2(mod9)V\equiv k^{2}\pmod 9,而模 99 的平方剩余只有 {0,1,4,7}\{0,1,4,7\} 四个值:

  • V≡1(mod9)V\equiv 1\pmod 9 只能来自 k=1,8k=1,8(12=11^2=1,82=64≡18^2=64\equiv 1);
  • V≡4(mod9)V\equiv 4\pmod 9 只能来自 k=2,7k=2,7;
  • V≡7(mod9)V\equiv 7\pmod 9 只能来自 k=4,5k=4,5;
  • V≡0(mod9)V\equiv 0\pmod 9 只能来自 k=3,6,9k=3,6,9。

模 9 余 2、3、5、6、8 的数一个都不是喜欢的数——这解释了样例里 [8,8][8,8] 答案是 00: 8,17,26,…8,17,26,\dots 这些模 9 余 8 的数永远排不出来。(顺便,题目把 d(x)d(x) 写成小写, 从样例反推取的就是数根 D(x)D(x),不是别的函数。)

再看每一组内部,重叠关系非常干净:

  • V≡1(mod9)V\equiv 1\pmod 9:k=1k=1 那一族要求 V≡1(mod9)V\equiv 1\pmod 9,它本身就是整类,没有额外整除条件; k=8k=8 要求 V≡1(mod9)V\equiv 1\pmod 9 且 8∣V8\mid V,是整类的子集。所以 k=8k=8 整族丢弃,这一类就是 V≡1(mod9)V\equiv 1\pmod 9。
  • V≡4(mod9)V\equiv 4\pmod 9:k=2k=2 给 {V≡4(mod18)}\{V\equiv 4\pmod{18}\},k=7k=7 给 {V≡49(mod63)}\{V\equiv 49\pmod{63}\}。 两族各自都蕴含 V≡4(mod9)V\equiv 4\pmod 9,交集是 V≡4(modlcm⁡(18,63)=126)V\equiv 4\pmod{\operatorname{lcm}(18,63)=126}, 即 V≡112(mod126)V\equiv 112\pmod{126},要扣一次。
  • V≡7(mod9)V\equiv 7\pmod 9:k=4k=4 给 {V≡16(mod36)}\{V\equiv 16\pmod{36}\},k=5k=5 给 {V≡25(mod45)}\{V\equiv 25\pmod{45}\}, 交集是 V≡7(modlcm⁡(36,45)=180)V\equiv 7\pmod{\operatorname{lcm}(36,45)=180},即 V≡160(mod180)V\equiv 160\pmod{180},要扣一次。
  • V≡0(mod9)V\equiv 0\pmod 9:k=3k=3 给 {V≡9(mod27)}\{V\equiv 9\pmod{27}\},k=9k=9 给 {81∣V}\{81\mid V\}, 两者互斥(81m81m 模 2727 恒为 0≠90\neq 9);k=6k=6 的 V≡36(mod54)V\equiv 36\pmod{54} 满足 36=27+936=27+9,整族落在 {V≡9(mod27)}\{V\equiv 9\pmod{27}\} 里,丢弃。

于是并集化成了七条同余式(外加两条容斥负项)的带符号求和。

族内怎么数? 首项 aa、公差 dd 的等差数列在 [1,N][1,N] 内的项数是

cnt(N,a,d)={⌊N−ad⌋+1,N⩾a0,N<a.\text{cnt}(N,a,d)=\begin{cases}\left\lfloor\dfrac{N-a}{d}\right\rfloor+1, & N\geqslant a\\ 0, & N<a.\end{cases}
前缀可减:[L,R][L,R] 的答案就是 f(R)−f(L−1)f(R)-f(L-1),其中 f(N)=∑±cnt(N,a,d)f(N)=\sum\pm\text{cnt}(N,a,d)。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:27
# update_at: 2026-10-08 04:27

import sys

# 每个元素是一族同余式(最小正解, 模数, 容斥符号);V 被"喜欢"当且仅当它落在其中任意一族。
# 由 D(x) = k <=> x ≡ k (mod 9) 推出 V = 9k*m + k^2,九族按 V mod 9 归并后只剩七个正族,
# 其中 k=2/k=7 与 k=4/k=5 两组有重叠,用两个 -1 项做容斥扣回。
type Term = tuple[int, int, int]  # (最小正解, 模数, 容斥符号)

TERMS: tuple[Term, ...] = (
    (1, 9, 1),      # k=1,也是整个 mod 9 == 1 类
    (4, 18, 1),     # k=2
    (49, 63, 1),    # k=7
    (16, 36, 1),    # k=4
    (25, 45, 1),    # k=5
    (9, 27, 1),     # k=3,也覆盖 k=6
    (81, 81, 1),    # k=9(81 | V,所以最小正解写 81 而不是 0)
    (112, 126, -1), # k=2 与 k=7 的重叠部分
    (160, 180, -1), # k=4 与 k=5 的重叠部分
)


def count_upto(n: int) -> int:
    """[1, n] 中"小D喜欢的数"的个数,即各族等差数列项数之和。"""
    return sum(
        sign * ((n - first) // mod + 1)  # 首项 first、公差 mod 的等差数列项数
        for first, mod, sign in TERMS
        if n >= first                    # n 小于首项时这一族一个都没有
    )


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)  # 数据组数
    out: list[str] = []
    for _ in range(T):
        L, R = next(data), next(data)
        out.append(str(count_upto(R) - count_upto(L - 1)))  # 前缀相减得区间计数
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:27
 * update_at: 2026-10-08 04:27
 */
// main.cpp:区间计数。把"V = x * D(x)"整形成若干同余数列的并集,每组用等差数列
// 计数、两组重叠用容斥扣掉,单次询问 O(1)。
// 与 main.py 同一算法:同一张同余式表,同样只做加减与整除。
//
// 数根性质:x >= 1 时 D(x) = k (1 <= k <= 9) 等价于 x ≡ k (mod 9)(余 0 记 9)。
// 固定 k 后 V = x * k,把 x = 9m + k (m >= 0) 代入得 V = 9k*m + k^2,即
//   k=1 -> V ≡ 1  (mod 9)     k=2 -> V ≡ 4  (mod 18)    k=3 -> V ≡ 9  (mod 27)
//   k=4 -> V ≡ 16 (mod 36)    k=5 -> V ≡ 25 (mod 45)    k=6 -> V ≡ 36 (mod 54)
//   k=7 -> V ≡ 49 (mod 63)    k=8 -> V ≡ 64 (mod 72)    k=9 -> V ≡ 0  (mod 81)
// 这九族按 V mod 9 归并(平方剩余只有 0/1/4/7,其余余数不可能出现):
//   mod 9 == 1:k=1 一族就是全部,k=8 被它包含,丢弃;
//   mod 9 == 4:k=2 与 k=7 的并集,交集 V ≡ 112 (mod 126) 要扣一次;
//   mod 9 == 7:k=4 与 k=5 的并集,交集 V ≡ 160 (mod 180) 要扣一次;
//   mod 9 == 0:k=3 的 {V ≡ 9 (mod 27)} 与 k=9 的 {81 | V},两者互斥;
//               k=6 的 V ≡ 36 (mod 54) 完全落在 V ≡ 9 (mod 27) 里,丢弃。
// 于是答案 = 表里各族等差数列项数的带符号求和,前缀相减得到区间计数。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 一族同余式对应一条等差数列:first 是它的最小正解,mod 是公差,
// sign 是该族在容斥中的系数(交集项为 -1)。
struct Term {
    ll first;
    ll mod;
    int sign;
};

const int TERM_CNT = 9; // 归并后剩下的同余式族数(含两条容斥负项)

// 首项必须写成最小正解:81 | V 的首项是 81 而不是 0,否则会把 V = 0 数进来。
const Term TERMS[TERM_CNT] = {
    {1, 9, 1},      // k=1,也是整个 mod 9 == 1 类
    {4, 18, 1},     // k=2
    {49, 63, 1},    // k=7
    {16, 36, 1},    // k=4
    {25, 45, 1},    // k=5
    {9, 27, 1},     // k=3,也覆盖 k=6
    {81, 81, 1},    // k=9(81 | V)
    {112, 126, -1}, // k=2 与 k=7 的重叠部分
    {160, 180, -1}, // k=4 与 k=5 的重叠部分
};

// [1, n] 中满足 V ≡ t.first (mod t.mod) 的正整数个数
ll cntResidue(ll n, const Term &t) {
    if (n < t.first) return 0;       // 这一族一个都没有,且避免负数进除法
    return (n - t.first) / t.mod + 1; // 首项 first、公差 mod 的等差数列项数
}

// [1, n] 中"小D喜欢的数"的个数
ll countUpto(ll n) {
    ll res = 0;
    for (int i = 0; i < TERM_CNT; ++i) {
        res += (ll)TERMS[i].sign * cntResidue(n, TERMS[i]);
    }
    return res;
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        ll L, R;
        if (scanf("%lld %lld", &L, &R) != 2) break;
        printf("%lld\n", countUpto(R) - countUpto(L - 1)); // L = 1 时传 0 进去,前缀为 0
    }
    return 0;
}

复杂度

  • 时间:每组询问算两次前缀,每次只做 9 次整除加一个 n<an<a 判断,O(1)O(1)。 T⩽20T\leqslant 20 时总计不到 400 次算术运算,实测 00 ms 级别(限时 1000 ms)。 对比:暴力枚举 xx 是 O(R)=O(1018)O(R)=O(10^{18}),本题正解相当于把 101810^{18} 次循环压成了 1818 次除法。
  • 空间:只存三条长度 9 的常量表和常数个变量,O(1)O(1),远低于 256 MB。
  • 数据类型:N−aN-a 最大约 101810^{18},long long 与 Python 大整数均无溢出风险; 只有余数项要小心写成 8181 而不是 00,否则会把 V=0V=0 数进来。

总结

  • 数根就是模 9 的余数:D(n)=1+(n−1) mod 9D(n)=1+(n-1)\bmod 9。凡是题目里出现"反复求数位和", 第一反应都应该是把它换成一次取模,因为递推求和的迭代次数无法进入状态转移, 而模 99 余数是常数大小的。
  • 固定参数族,把问题变成等差数列:D(x)=kD(x)=k 意味着 x≡k(mod9)x\equiv k\pmod 9, 于是 V=x⋅kV=x\cdot k 关于 kk 自动成为一个公差 9k9k 的等差序列, “能力"被翻译成"离散的若干等差数列”,计数就只剩整除与容斥。
  • 重叠只在 V mod 9V\bmod 9 相同的组内:同余值不同就一定不重叠,所以可以按 V mod 9V\bmod 9 分组独立处理,每组内最多两族的交集用 lcm⁡\operatorname{lcm} 显式算出来扣掉。 判别"哪些族可以整族丢弃"的标准就是看它是否被同组里更宽的族包含。
  • 模 9 的平方剩余只有 {0,1,4,7}\{0,1,4,7\}:这是"为什么答案只由这四类余数组成"的 一句话解释,也是本题排除掉一大半候选数的原因(余 2,3,5,6,82,3,5,6,8 的数永远不喜欢)。
  • 前缀相减处理 L=1L=1:f(0)f(0) 必须返回 00;实现上先判 N<aN<a 再进除法, 既避免负数除法,也避免把 00 当成"81∣081\mid 0"的解。

数据来源说明:本题素材来自一本通·高手训练篇,随题数据目录里带有生成脚本 (data.py),说明测试点是自造的、题面也可能经过网络重建,与官方原题的数据强度 可能存在差异。本文的结论以随题 data/ 的 10 个测试点全过为准,未与官方评测机比对。