自动搬运

查看原文

来自洛谷，原作者为

	OIer991215 ？

搬运于2025-08-24 22:05:31，当前版本为作者最后更新于2018-10-28 01:28:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看一下数据氛围！数据范围疯狂暗示着O（1）做法。


观察 l，l+1，l+2，l+3，...，r-1，r，这些数字之间去掉逗号之后，成了一个巨大的数，然而模数是9，很小。那么为什么模数是9呢？于是突破点就来了。


继续观察l，l+1，l+2，l+3，...，r-1，r。 这些数字之前一旦去掉了逗号，那么上述数字对最后巨大数字的贡献是10的若干次方。

也就是 l*(10)^? + (l+1)*(10)^? + ... + (r)*(10)^?    （？代表“若干”）.


10的若干次方 除以 9 的余数  恒为 1 ！！！

那么 l*（10）^? % 9 = l%9。

那么上面那堆数字组起来的大数除以9的余数 就 等同于 那堆数字加起来乘1除以9的余数。

而这些数字之间只相差1，那么根据等差数列求和公式，O（1）计算答案就好了。

等差数列求和里有模运算，也有除法运算，那么把分母转化成逆元（2在模9的意义下 逆元是5）

于是这题就解决了 代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		long long l,r;
		cin>>l>>r;
		long long cnt=(r-l+1)%9;;
		long long ans=cnt*(l%9)%9+(cnt)*(cnt-1)%9*5%9;
		cout<<ans%9<<endl;
	}
	return 0;
}