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

时间:2022-06-25 18:55:02

题目

小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与序号对3取余的余数有关,余数为0和2时可以整除,而每三个数中会有两个数能整除2。因此只需要计算序号中有多少个余数为3的,如果左右两端差值刚好为3的倍数时,可是直接计算整除3的数字个数:

c o u n t = ( r l ) / 3 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;
    }

}