牛客網 2019校招真題程式設計題 被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整除。

思路

被三整除，那麼各位的和一定是能夠被三整除的，因為此題的第i位數是由1-i個數組成的，是以自然想到了等差數列求和公式，但是還是要挨個計算，于是就試着寫下了每個數的和，發現每三個數為一個周期，和的餘數為 1,0,0，我們可以利用這個性質找出第1到n一共有多少個三個一組的，然後*2就是這些組中能被三整除的總數，再單獨處理餘下的不足為3組的一組，如果n%3==2，那麼需要再加1，這樣就求出了1-n一共有多少數被n整除，然後我們分别求出1到l-1和1-r中被3整除的總數numl，numr,用numr-numl即可得出答案。

代碼如下

#include <bits/stdc++.h>
using namespace std;
int l,r;
int main()
{
    scanf("%d%d",&l,&r);
    int numl = (l-1)/3*2;
    if((l-1)%3==2) numl++;
    int numr = r/3*2;
    if(r%3==2) numr++;
    printf("%d\n",numr-numl);
    return 0;
}