1. 题目描述

problem link

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

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

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

输入描述：

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

输出描述：

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

示例：

// 输入
2 5
// 输出
3
// 说明
12, 123, 1234, 12345...
其中12, 123, 12345能被3整除。

2. 解题

首先基于两个简单的规律：

1. 将一个数的各位数字相加，若所得数字能被3整除，则原数字也能被3整除。
2. 一个多位数除3的余数等于其各位数相加除3的余数。

首先，将求第l项到第r项内所有能被3整除的数的个数先简化为求第1项到第r项所有能被3整除的数的个数。

然后从r等于1开始分析，我们主要关注这个数的各位数相加然后除3的余数是多少，为0则可以被3整除。可知r为1的时候该数为1，则除3余1。

现在r等于2，此时该数为12，这个数可以被分为两部分，即之前的1和现在的2。则12除3的余数为1除3余1加上2除3余2，所以余0，即能被3整除。

现在r等于3，此时该数为123，这个数同样也可以被分为两部分，即之前的12和现在的3。则123除3的余数为12除3余0加上3除3余0，所以余0，即能被3整除。

依次类推，可知每次后面的那部分的数字除3的余数是一个0、1、2的循环，所以可以总结出来前r项中能被3整除的数的个数的规律：

r   : 1 2 3 4 5 6 7 8 9
cnt : 0 1 2 2 3 4 4 5 6

3. 代码

#include <iostream>
using namespace std;

int Cnt(int num) {
    int res = 2 * (num / 3);
    if(num % 3 == 2) {
        res++;
    }
    
    return res;
}

int main() {
    int l, r;
    while(cin >> l >> r) {
        if(l == 1) {
            cout << Cnt(r) << endl;
        }
        else {
            cout << Cnt(r) - Cnt(l - 1) << endl;
        }
    }
}