網易2018實習生筆試題 被三整除

時間限制：1秒

空間限制：32768K

問題描述：

小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，12，123，1234，12345，123456。。。。。。能被三整除的規律為：不能，能，能，不能，能，能。。。。。。，以三為周期循環，因而将輸入的l，r分别移動至一個周期的第一個位置，在移動過程中标記需要剔除新引入的能被三整除的數目count1，标記需要加上移動過程中删除的能被三整除的數目count，再按公式（r-l）/3*2-count1+count，即可求得能被三整除的數目。

#include<stdio.h>
int main()
{
    int l,r;
    int count = 0,count1 = 0,result = 0;
    scanf("%d%d",&l,&r);
    while(l%3 != 1)
    {
        if(l%3 == 0) 
        {
            l--;
            count1++;
        }
        if(l%3 == 2) 
            l--;
    }                     
    while(r%3 != 1)
    {
        if(r%3 == 0)
        {
            count++;
            r--;
        }
        if(r%3 == 2)
        {
            count++;
            r--;
        }
    }
    result = (r-l)/3*2 - count1 + count;
    printf("%d\n",result);
}