题解 P4942 【小凯的数字】

· · 题解 

首先看一下数据氛围！数据范围疯狂暗示着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;
}