小凯的数字

1 核心观察 (Key Observation)

题目要求我们将 $l$ 到 $r$ 之间的所有整数拼接成一个大数 $N$，并求 $N \pmod 9$。 例如：$l=2, r=5 \implies N=2345$。

我们利用 模 9 的整除特征：

一个数模 9 的余数，等于其各位数字之和模 9 的余数。

$$x \equiv S(x) \pmod 9$$

证明:

这是解题最关键的一步。

• 知识点： 一个十进制数 $n$ 与其各位数字之和在模 $9$ 的意义下是同余的。

• 数学表达： 设 $S(n)$ 为 $n$ 的各位数字之和，则：

  $$n \equiv S(n) \pmod 9$$

• 原理： 因为 $10 \equiv 1 \pmod 9$，所以 $10^k \equiv 1^k \equiv 1 \pmod 9$(同余相乘性质)。 对于任意数字，例如 $357 = 3 \times 100 + 5 \times 10 + 7$，在模 9 下：

  $$3 \times 100 + 5 \times 10 + 7 \equiv 3 \times 1 + 5 \times 1 + 7 \equiv 3+5+7 \pmod 9$$

2. 同余的可加性

这一性质将“拼接问题”转化为了“求和问题”。

• 分析： 题目中的数字是由 $l$ 到 $r$ 拼接而成的。 例如 $l=8, r=12$，数字是 $89101112$。 这个大数的模 9 余数，等于其所有数位之和的模 9 余数。
• 转化： 所有数位之和，其实就是把 $l, l+1, \dots, r$ 每个数字拆开相加。 由第 1 点可知，每个数字 $x$ 的数位和 $\equiv x \pmod 9$。 结论： 拼接起来的大数 $N$ 模 9 的余数，等于数列 $l$ 到 $r$ 的数值之和模 9 的余数。
  $$\text{Answer} = \left( \sum_{i=l}^{r} i \right) \bmod 9$$

拼接后的数 $N$ 的“各位数字之和”，实际上等价于区间 $[l, r]$ 内所有整数的“各位数字之和”的总和。 利用同余性质 $S(i) \equiv i \pmod 9$，我们可以得出结论：

也就是：拼接数 $N$ 模 9 的余数 $=$ 等差数列 $[l, r]$ 的和模 9 的余数。

举个例子：如果 $l = 12,\ r = 14$，则拼接得到 $N=121314$。直接求各位数字和：

• $S(N)=1+2+1+3+1+4=12 \equiv 3 \pmod 9.$
• $(1+2)+(1+3)+(1+4)=12 \equiv 3 \pmod 9.$
• $S(12)+S(13)+S(14)=12 \equiv 3 \pmod 9.$
• $12+13+14=39 \equiv 3 \pmod 9.$

使用我们的方法，区间和为

题目核心
拼接数 $N$ 模 9 的余数 $=$ 等差数列 $[l, r]$ 的和模 9 的余数。
把拼接转换成求和，从而简化问题。

2 数学推导 (Derivation)

我们需要计算等差数列和：

由于 $l, r \le 10^{12}$，直接计算乘积会爆 long long，且我们涉及除法运算，不能直接对分子取模。这里有两种处理方法。

方法一：乘法逆元 (Modular Inverse) —— 推荐

在模运算中，除以一个数等价于乘以这个数的逆元。 我们需要计算 $/ 2 \pmod 9$。因为 $\gcd(2, 9) = 1$，逆元存在。 寻找一个 $x$ 使得 $2x \equiv 1 \pmod 9$。显而易见 $2 \times 5 = 10 \equiv 1 \pmod 9$。

所以，除以 2 等价于乘以 5。 公式转化为：

这种方法全程取模，完全不需要大整数类型，也不用担心溢出。

方法二：扩展模数 (Expanding Modulus)

如果我们不知道逆元，也可以利用性质：

若 $A/2 = B \pmod 9$，则 $A = 2B \pmod{18}$。

原理是：我们需要求 $B$，而 $B < 9$，这保证了 $2B < 18$。 所以 $2B \pmod{18}$ 的结果就是 $2B$ 本身（不会发生截断）。我们只需要算出分子对 $18$ 取模的结果，然后直接除以 2 即可还原出 $B$。

公式转化为：

3 代码实现 (Implementation)

使用 方法一（乘法逆元） 的 C++ 代码，简洁且安全。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

int n;
ll l,r;
int main (int argc, char *argv[]) {
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> l >> r;
        ll sum_lr = (l+r) % 9;
        ll len = (r-l+1) % 9;

        ll ans = ( sum_lr * len * 5) %9;
        std::cout << ans << "\n";
    }
    
    return 0;
}

    

复杂度分析

• 时间复杂度： $O(1)$，仅需常数次算术运算。
• 空间复杂度： $O(1)$。

解法2: 更神奇的性质

直接暴力,找规律.

观察到，

任意连续 9 个数字的和，模 9 的余数为 0。 例如：$1+2+3+4+5+6+7+8+9=45 \equiv 0 \pmod 9$。

证明:

因此，我们可以将区间 $[l, r]$ 分成若干个长度为 9 的完整区间，以及剩余的部分。 完整区间的和模 9 为 0，只需要计算剩余部分的和即可。

代码

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

        #include <iostream>

using namespace std;

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    int Q;
    cin >> Q;
    while (Q--) {
        long long l, r;
        cin >> l >> r;

        // 1. 算出总长度
        long long len = r - l + 1;
        
        // 2. 算出除以9之后的余数（也就是需要计算的数的个数）
        //    如果能被9整除，remain就是0，循环都不用进，直接输出0
        long long remain = len % 9;
        
        long long ans = 0;
        
        // 3. 只计算这剩下的几个数即可
        //    循环最多跑 8 次，飞快！
        for (int i = 0; i < remain; i++) {
            ans = (ans + (l + i)) % 9;
        }
        
        cout << ans << "\n";
    }
    return 0;
}


    

解法3: 不用求逆元

这是一份针对你这段代码的简洁版题解，适合放在博客或题解区。它强调了代码中“奇偶性判断”的巧妙之处。

题目要求计算 $l$ 到 $r$ 所有数字拼接后的模 9 余数。根据模 9 的同余性质，这等价于求 数列 $[l, r]$ 的和模 9。

我们使用等差数列求和公式：

这段代码并没有直接套用公式计算（因为直接相乘会爆 long long），而是采用了一个非常聪明的**“先除后乘”**策略。

设 $A = l + r$（首尾和），$B = r - l + 1$（项数）。 公式即为：$\frac{A \times B}{2}$。

关键点：奇偶性判断

因为数列的和一定是整数，所以分子 $A \times B$ 一定是偶数。这意味着 $A$ 和 $B$ 中至少有一个是偶数。

代码通过 if 判断来处理这个除法：

        
1
2
3
4
5

        if (a % 2 == 0)
    a /= 2;  // 如果 A 是偶数，直接让 A 除以 2
else
    b /= 2;  // 如果 A 是奇数，那么 B 一定是偶数，让 B 除以 2

    

结果计算

经过上面的处理，分母的 $2$ 已经被消除，且 $A$ 和 $B$ 仍然都在 long long 的安全范围内。 此时问题转化为求 $A \times B \pmod 9$。根据同余性质：

代码直接输出：

        
1
2

        cout << ((a % 9) * (b % 9)) % 9 << endl;

    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

        #include<bits/stdc++.h>
using namespace std;
long long q, l, r,a,b;
int main() {
	cin >> q;
	while (q--) {
		cin >> l >> r;
		a = l + r;
		b = r - l + 1;
		if (a % 2 == 0)
			a /= 2;
		else
			b /= 2;
		cout << ((a % 9) * (b % 9)) % 9 << endl;
	}
	return 0;
}