题目概述
题目描述
小凯有一天突发奇想,写下了一串数字: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解释:2345mod9=589101112mod9=5
数据范围
30% 数据满足:Q≤10;l,r≤100
50% 数据满足:Q≤100;l,r≤104
70% 数据满足:Q≤1000;l,r≤106
100%数据满足:Q≤104;0<l,r≤1012 且 l≤r
解题报告
题意理解
自己看题吧,我懒了
算法解析
首先你得有小学数论知识.
a≡0mod
也就是说,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;
}