$\texttt{Description}$

给定 $l$，$r$，求 $\overline l \quad \overline{(l + 1)} \quad \overline{(l + 2)}\quad \cdots \quad \overline{(r - 1)} \quad \overline{(r)} \quad \% \quad9$ 的值。

$\texttt{Solution}$

看到 $\mod 9$，容易想到该性质：

$$X \mod 9 = (x_1 \mod 9 + x_2 \mod 9 + \cdots + x_n \mod 9) \mod 9$$

其中， $x_1$ 表示 $X$ 的最高位，$x_n$ 表示 $X$ 的最低位（即个位）。

通俗地说，就是：一个数除以 $9$ 的余数等于它各个位上的数除以 $9$ 的余数之和再除以 $9$ 的余数。

证明很简单：

首先，$X$ 可以写成如下形式：$x_1 \times 10^n + x_2 \times 10^{n - 1} + \cdots + x_{n - 1} \times 10^1 + x_n \times 10^0$。

考虑对 $10^i$ 进行拆分，显然，对于任何一个 $10^i$，有 $10^i = (\sum\limits_{j = 0}^{i - 1} 9 \times 10^{j}) + 1$。

那么 $X$ 就可以写为：

$$\left[(x_1 \times \sum\limits_{j = 0}^{n - 1} 9 \times 10^{j}) + x_1 \times 1 \right] + \left[(x_2 \times \sum\limits_{j = 0}^{n - 2} 9 \times 10^{j}) + x_2 \times 1 \right] + \cdots + \left[(x_{n - 1} \times \sum\limits_{j = 0}^{0} 9 \times 10^{j}) + x_{n - 1} \times 1 \right] + x_n$$

很显然，对于任何的 $\sum\limits_{j = 0}^{i - 1} 9 \times 10^{j} \mod 9$，结果一定等于 $0$。

于是 $X \mod 9$ 就等于 $(x_1 + x_2 + \cdots + x_n) \mod 9$，也就是 $(x_1 \mod 9 + x_2 \mod 9 + \cdots + x_n \mod 9) \mod 9$。

那么这题就可以转化为求 $\sum\limits_{i = l}^r i \mod 9$ 的值，用等差数列求和公式可以做到每个问题 $\mathcal{O}(1)$ 解决。

需要注意的是，在使用等差数列求和公式的时候，由于 $\dfrac{(l + r) \times (r - l + 1)}{2}$ 的分母太大，即使用 $\texttt{long long}$ 也会溢出，所以可以判断 $(l + r)$ 和 $(r - l + 1)$ 的奇偶性，把偶数的那个先除以 $2$，模 $9$，再把另一个数模 $9$。最后两数相乘，模 $9$。

$\texttt{AC Code}$

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

#define int long long
int q;

signed main() {
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int a = l + r, b = r - l + 1;
        (a % 2 == 0) ? (a /= 2) : (b /= 2);
        cout << ((a % 9) * (b % 9)) % 9 << endl;
    }
    return 0;
}