刷题笔记：牛客网易笔试题——被3整除

题目

小Q得到一个神奇的数列: 1, 12,123,…12345678910,1234567891011…。
并且小Q对于能否被3整除这个性质很感兴趣。
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。

输入描述:

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

输出描述:

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

示例1
输入

2 5

输出

3

说明

12, 123, 1234, 12345…
其中12, 123, 12345能被3整除。

思路

注意输入的区间两端与数列的对应关系，比如第十个数应该是12345678910，10是两位数字补在123456789后边。

最初我的想法是按位求和，看是否能被3整除，这样算法复杂度太高，测试没有通过，于是考虑找规律。

写出一部分数据（点击看大图）：

可以发现，是否整除3与序号对3取余的余数有关，余数为0和2时可以整除，而每三个数中会有两个数能整除2。因此只需要计算序号中有多少个余数为3的，如果左右两端差值刚好为3的倍数时，可是直接计算整除3的数字个数：

count=(r−l)/3∗2 $$count=(r-l)/3\ast 2$$

而实际左右两端差值不一定是3的倍数，因此先计算整除3的个数：

count=(r/3-l/3)*2;

然后计算左右端多出的余数：

if(l%3==0)
   count++;
if(r%3==2)
   count++;

代码

#include <iostream> 

using namespace std;  

int main()
{
    int l,r;
    int count=0;
    while(cin>>l>>r)
    {
        count=(r/3-l/3)*2;
        if(l%3==0)
            count++;
        if(r%3==2)
            count++;
        cout<<count;
    }

}