题目描述

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

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

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

实现思路

1. 按照数字排列，每增加3个数字中油两个数字都可以被3整除，因为是按照1,2,3,4,5,6的顺序拍下去的，1+2可以被3整除，3本身可以被3整除，那么添加到里面的数字只有剩下一个3n+1的数字时就表示这个组合数不能被3整除
2. 那么首先根据左右两个区间可以得到该区间数据的总数，就是total = r-l+1
3. 查找区间中表示3n+1的个数：首先从左边开始找到一个是3n+1的数startIndex，然后从右边搜素找到一个数可以表示endIndex，最后用(endIndex-startIndex)/3+1表示中间有多少个这样的数据
4. 做差值既可以得到结果

源代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r = sc.nextInt();
        int total = r - l + 1;
        int result = total;
        int startIndex = -1;
        int endIndex = -1;
        for (int i=l; i<=r; i++) {
            if ((i-1)%3==0) {
                startIndex = i;
                break;
            }
        }
        for (int i=r; i>=l; i--) {
            if ((i-1)%3==0) {
                endIndex = i;
                break;
            }
        }
        if (startIndex != -1) {
            int noThree = (endIndex - startIndex)/3 + 1;
            result = total - noThree;
        }
        System.out.println(result);
    }
}