题目描述

小凯有一天突发奇想，写下了一串数字：$l(l+1)(l+2)…(r-1)r$

例如：$l=2,r=5$ 时，数字为：$2345$

$l=8,r=12$ 时数字为：$89101112$

小凯很喜欢数字 $9$，所以他想问你他写下的数字除以 $9$ 的余数是多少

例如：$l=2,r=5$ 时，$2345\text{ mod }9 = 5$

输入格式

第一行为数字 $Q$，表示小凯有 $Q$ 个问题

第 $2 \sim Q+1$ 行，每行两个数字 $l,r$ 表示数字范围

输出格式

对于每行的问题输出一行，一个数字，表示小凯问题的回答

输入样例1

2
2 5
8 12

输出样例1

5
5

输入样例2

3
1 999
123 456
13579 24680

输出样例2

0
6
0

秦大佬题解{:target=”_blank”}（他的做法好像在l,r差值极大时会T啊）

算法

(数论,数学) $O(Q)$

结论：$x\ \text{mod}\ 9 = x的各位数字之和\ \text{mod}\ 9$

证明：
设 $x$ 的第 $i$ 位（从低位到高位算）为 $a _ i$，那么 $x = 10 ^ {n - 1} a _ n + 10 ^ {n - 2} a _ {n - 1} + \cdots + 10 a _ 2 + a _ 1$
则 $x\ \text{mod}\ 9 = (10 ^ {n - 1} a _ n + 10 ^ {n - 2} a _ {n - 1} + \cdots + 10 a _ 2 + a _ 1)\ \text{mod}\ 9$
$ = 10 ^ {n - 1} a _ n\ \text{mod}\ 9 + \cdots + 10 a _ 2\ \text{mod}\ 9 + a _ 1\ \text{mod}\ 9$
由于 $10 ^ k\ \text{mod}\ 9 = 1(k \in N)$
所以 $x = a _ n\ \text{mod}\ 9 + a _ {n - 1}\ \text{mod}\ 9 + \cdots + a _ 1\ \text{mod}\ 9$
$ = (a _ 1 + a _ 2 + \cdots + a _ n)\ \text{mod}\ 9$

所以对于 $l(l+1)(l+2)…(r-1)r\ \text{mod}\ 9$，$(l + \cdots + r)\ \text{mod}\ 9$ 即为答案

对于 $l + \cdots + r$，有公式 $l + \cdots + r = \displaystyle \frac {(l + r)(r - l + 1)} 2$

涉及到除法，不好取模，可以先特判下 $l + r$ 和 $r - l + 1$ 哪个是 $2$ 的倍数，将其除 $2$，再进行取模

时间复杂度

一共要询问 $Q$ 次，
每次询问只用 $\mathcal O(1)$ 的时间即可得出答案，
所以总的时间复杂度为 $\mathcal O(Q)$

C++ 代码

#include <stdio.h>

typedef long long ll; // 10 ^ 12 爆 int

int Q;
ll l,r;
ll m1,m2; // 用于特判哪个是 2 的倍数

int main()
{
    for (scanf("%d", &Q); Q -- ;)
    {
        scanf("%lld %lld", &l, &r);
        m2 = l + r, m1 = r - l + 1; // 分别找到分子中的两个数
        if (m2 & 1) m1 >>= 1; // 如果 m2 是奇数，则 m1 是偶数
        else        m2 >>= 1; // 否则 m2 是偶数
        m1 %= 9, m2 %= 9;     // 分别 mod 9
        printf("%lld\n", m1 * m2 % 9); // 输出积 mod 9 的结果
    }
    return 0;
}