更好的阅读体验

题目概述

题目描述

小凯有一天突发奇想，写下了一串数字：$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 mod 9 = 5

输入输出格式

输入格式

第一行为数字Q,表示小凯有Q个问题 第2-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

样例解释

样例1解释：$2345 \quad mod \quad 9 = 5 \quad \\\\ 89101112 \quad mod \quad 9 = 5$

数据范围

30% 数据满足：$Q \le 10;l,r \le 100$
50% 数据满足：$Q \le 100;l,r \le {10}^4$
70% 数据满足：$Q \le 1000;l,r \le {10}^6$
100%数据满足：$Q \le 10^4;0<l,r \le 10^{12}$ 且 $l \le r$

解题报告

题意理解

自己看题吧,我懒了

算法解析

首先你得有小学数论知识.
$$ a \equiv 0 \bmod 9 \Rightarrow a的数字和是9的倍数 $$
也就是说,$a$是$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 $$
他们数字和模$9$是多少呢?
$$ 0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,2,3,4 $$
假如我问你,$[1,13]$,他们构成的数字,模$9$是多少
$$ 12345678910111213 $$
然后等量代换
$$ 1+2+3+4+5+6+7+8+9+10+11+12+13 $$
或者说
$$ 1+2+3+4+5+6+7+8+0+1+2+3+4 $$
其实还可以是
$$ 1+2+3+4 $$
最后就是
$$ 10 \equiv 1 \bmod 9 $$
因此我们可以得出.

我们容易发现，对于任意的九个连续自然数，记为
$$ a_1,a_2,a_3 \dots a_9 $$
这九个数字的每一位数字之和必被九整除。

证明一下.
$$ a_1 数字和为x \\\\x+(x+1)+\dots (x+9) \equiv 9 \times x+(1+2+3+\dots9) \equiv 45 \bmod 9 \equiv 0 \bmod 9 $$
然后这道题,就可以愉快的结束了.
$$ len=r-l+1 \quad len为区间[l,r]长度 \\\\len=9 \times a+b \\\\因此我们只需要求出b长度个数的模9余数即可 $$

代码解析

#include <bits/stdc++.h>
using namespace std;
long long ans,T,l,r,w,x,len;
inline void work()
{
    ans=0;
    len=r-l+1,w=len%9;//剩下的长度
    l=r-w+1;//截取剩下
    while(l<=r)
    {
        x=l;
        while (x)//数字分解
        {
            ans+=(x%10);
            x/=10;
        }
        ans%=9;
        l++;
    }
    ans%=9;
    cout<<ans<<endl;
}
inline void init()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while (T--)
    {
        cin>>l>>r;
        work();
    }
}
int main()
{
    init();
    return 0;
}