题解 P4942 【小凯的数字】

· · 题解

数论好题

犹记五年级时，小学数学老师拿着占来的体育课给我们拓展9的整除特性

有一句话让我印象很深刻：

判断一个数能否被9整除，可以把这个数按数位随便“切”

把“切”下来的数加起来，所得到的数能被9整除，原数就能被整除

（也就是得到的数与原数关于9同余）

当时我学的东西太少，听不懂这么高深的理论

老师就举了个例子：

比如说12345
可以先在个位和十位切一刀-> 1|2345
然后在百位和千位切一刀-> 1|23|45
那我们切出来3个数：1,23,45
求和 1+23+45=69
69不能被9整除，因此原数12345不能被9整除
当然，切哪里随便，你也可以切4刀把12345变成1|2|3|4|5
然后求和 1+2+3+4+5=15
15不能被9整除，因此原数12345不能被9整除
有没有发现这种情况就是我们一开始学的把各位数加起来判断的方法？

但是为什么呢？

从最简单的情况出发

如果有一个三位数为abc，其中a为百位，b为十位，c为个位

则a+b+c\equivabc(mod9)

由于a+b\equivab(mod9)

故ab+c\equivabc(mod9)

同理可得a+bc\equivabc(mod9)

推广，若有一个N位数a_ {1}a_ {2} \ldots a_{N}

则有a_{1} \ldots a_ {i} + a_ {i+1} \ldots a_ {N} \equiva_ {1}a_ {2} \ldots a_ {N}

因此，这道题就迎刃而解了：

把l到r之间的整数加起来,输出它模9的结果

就是求一个等差数列的和，求和公式：

sum$ = $(l+r)$ $\cdot$ $(r-l+1)/2

由于l+r和r-l+1中至少有一个为偶数

那我们找到这个偶数，除以2

最后对它们分别取模

输出，搞定！

代码来了~

#include<iostream> 
#include<cstdio>
#define ll long long//宏定义，省事
using namespace std;
int main(){
    int n;
    ll l,r,sum;//注意数据范围为longlong
    cin>>n;
    for(int i=1;i<=n;++i){//n次询问
        scanf("%lld%lld",&l,&r);//首项、末项
        ll t1=l+r,t2=r-l+1;
        if(t1&1) t2/=2;//位运算判断t1是否为奇数
    //t1是奇数，那t2就是偶数，除以2     
        else t1/=2;
    //t1是偶数，那就直接除以2
        sum=t1%9;//分别取模
        sum*=t2%9;
        printf("%d\n",sum%9);//输出
    }
    return 0;
}

你AC了吗？AC了就点个赞呗