由数根与模 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
形式化题目
对正整数
给出
注意"不同的"是硬要求:同一个
正解
思路
朴素做法。 枚举
换方向:枚举
突破口是数根的同余本质。 数根有两个等价刻画,这是全题的钥匙:
也就是说,一个正整数
固定数根
也就是说,
| 数根 |
生成的 |
同余式 | |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | |||
| 9 |
九族各自是一个等差数列,"喜欢的数"就是这九个等差数列集合并起来。于是问题变成 “求并集中落在区间内的元素个数”,只剩两件事:族内计数(整除)与族间去重(容斥)。
关键观察:这九族按
只能来自 ( , ); 只能来自 ; 只能来自 ; 只能来自 。
模 9 余 2、3、5、6、8 的数一个都不是喜欢的数——这解释了样例里
再看每一组内部,重叠关系非常干净:
: 那一族要求 ,它本身就是整类,没有额外整除条件; 要求 且 ,是整类的子集。所以 整族丢弃,这一类就是 。 : 给 , 给 。 两族各自都蕴含 ,交集是 , 即 ,要扣一次。 : 给 , 给 , 交集是 ,即 ,要扣一次。 : 给 , 给 , 两者互斥( 模 恒为 ); 的 满足 ,整族落在 里,丢弃。
于是并集化成了七条同余式(外加两条容斥负项)的带符号求和。
族内怎么数? 首项
代码
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++ 版(同一算法):
/**
* 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 次整除加一个
判断, 。 时总计不到 400 次算术运算,实测 ms 级别(限时 1000 ms)。 对比:暴力枚举 是 ,本题正解相当于把 次循环压成了 次除法。 - 空间:只存三条长度 9 的常量表和常数个变量,
,远低于 256 MB。 - 数据类型:
最大约 , long long与 Python 大整数均无溢出风险; 只有余数项要小心写成而不是 ,否则会把 数进来。
总结
- 数根就是模 9 的余数:
。凡是题目里出现"反复求数位和", 第一反应都应该是把它换成一次取模,因为递推求和的迭代次数无法进入状态转移, 而模 余数是常数大小的。 - 固定参数族,把问题变成等差数列:
意味着 , 于是 关于 自动成为一个公差 的等差序列, “能力"被翻译成"离散的若干等差数列”,计数就只剩整除与容斥。 - 重叠只在
相同的组内:同余值不同就一定不重叠,所以可以按 分组独立处理,每组内最多两族的交集用 显式算出来扣掉。 判别"哪些族可以整族丢弃"的标准就是看它是否被同组里更宽的族包含。 - 模 9 的平方剩余只有
:这是"为什么答案只由这四类余数组成"的 一句话解释,也是本题排除掉一大半候选数的原因(余 的数永远不喜欢)。 - 前缀相减处理
: 必须返回 ;实现上先判 再进除法, 既避免负数除法,也避免把 当成" "的解。
数据来源说明:本题素材来自一本通·高手训练篇,随题数据目录里带有生成脚本 (
data.py),说明测试点是自造的、题面也可能经过网络重建,与官方原题的数据强度 可能存在差异。本文的结论以随题data/的 10 个测试点全过为准,未与官方评测机比对。