笔试刷题-网易2018-06-11

题目描述：

/**
小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。

并且小Q对于能否被3整除这个性质很感兴趣。

小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。


输入描述:
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。


输出描述:
输出一个整数, 表示区间内能被3整除的数字个数。

输入例子1:
2 5

输出例子1:
3

例子说明1:
12, 123, 1234, 12345...
其中12, 123, 12345能被3整除。
*/

思路如下：

/**
1,2,3,4,5,...,9,10,11,12,...,1000
上述组成的数字其是否被3整除其实跟
1+2+3+4...+10+11...+1000是膜3同余
以10这个数字拼的来看
123 __ __ __ __还有10^tail次方
可以看车个(10^tail-1)*123+123 tail>=0
若依仅仅这么看10^tail-1肯定膜3余为0
问题已经转化成累计和mod3的问题了

1到l-1累积和 mod3的余数作为开始
设l-r共N个数

0: 1 2 0循环
1到l-1累积和为0
那么从l开始产生的累积和mod3数列如下
0+1(这个0是1到l-1累积mod3为0, 1是l%3), (1+2)%3=0(1是1到l+1累积和mod3 2是l+2mod3),
那么mod循环序列为 1 0 0 1 0 0如此计算0的个数即可

其他两个情形类似，注意尾巴的处理，具体见代码
1: 2 0 1 循环
2: 0 1 2 循环

*/

代码如下：

#include<stdio.h>
#include<iostream>

typedef long long LL;

using namespace std;

int main(){
    LL l, r, lastMod=0, res=0, N;
    scanf("%lld%lld", &l, &r);
    N=r-l+1;
    lastMod=(l-1)*l/2;
    lastMod%=3;
    if(lastMod==0){
        res=2*(N/3);
        if(N%3==2)
            res+=1;
    }
    else if(lastMod==1){
        res=2*(N/3);
        if(N%3==1)
            res+=1;
        else if(N%3==2)
            res+=2;
    }
    else if(lastMod==2){
        res=N/3;
        if(N%2==2)
            res+=1;
    }
    printf("%lld", res);
    return 0;
}