小凯的数字

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 \equiv \sum_{i=l}^r S(i) \equiv \sum_{i=l}^r 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.$

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

\text{Sum}=\frac{(12+14)\times(14-12+1)}{2}=\frac{26\times3}{2}=39\equiv3\pmod9.

或者模运算步骤：

(l+r)\bmod9=26\bmod9=8,\ (r-l+1)\bmod9=3

，因此

\text{Ans}=(8\times3\times5)\bmod9=120\bmod9=3.

三种方法一致，答案为

3

。

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

2 数学推导 (Derivation)

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

\text{Sum} = \frac{(l+r)(r-l+1)}{2}

最终答案为

\text{Sum} \bmod 9

。

由于 $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。公式转化为：

\text{Ans} = \left[ (l+r) \times (r-l+1) \times 5 \right] \bmod 9

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

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

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

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

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

公式转化为：

\text{Ans} = \left[ (l+r)(r-l+1) \bmod{18} \right] / 2

3 代码实现 (Implementation)

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

cpp

#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$ 。

证明:

(n+1) + (n+2) + \dots + (n+9) = 9n + (1+2+\dots+9) = 9n + 45 \equiv 0 \pmod 9

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

代码

cpp

#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。

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

\text{Sum} = \frac{(l+r) \times (r-l+1)}{2}

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

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

关键点：奇偶性判断

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

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

cpp

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$ 。根据同余性质：

(A \times B) \pmod 9 = \left( (A \bmod 9) \times (B \bmod 9) \right) \pmod 9

代码直接输出：

cpp

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

cpp

#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;
}

目录