2018 网易 iOS [编程题] 被3整除

[TOC]

小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整除。

---

错误的代码（通过率70% ~~~~ 可能是运气）

/*
 网易 iOS 编程题-被3整除-错误版
 
 这道题里设置的数值上限为 1e9 也就是 1000000000
 int 值的 范围为  -2147483648～2147483647
 当 r >= 10 的时候，有趣的数就已经超过 int 值得范围了，就算是 long int 也拯救不了 r 到 1e9 那么大的范围
 所以在范围内有趣的数需要换一个方式呈现
 能被三整除的数，其 “各位和” 也能被三整除
 */

/*
    这里的错误在于，以 getQNum 为例，
    当 index = 10 时，result 应该是 1+2+...+9+1+0,
    程序里设定的 result = 1+2+...+9+10;
    同理在计算 value 值时有一样的错误
*/


#include <iostream>

int isQNum(int num){
    return (num%3 ? 0:1);
}

int getQNum(int index){
    int result = 0;
    for(int i = 1; i <= index; i++){
        result += i;
    }
    return result;
}

using namespace std;
int main(int argc, char *argv[]) {
    
    int l, r;
    int allQ = 0;
    
    cin >> l >> r;
    
    int value = getQNum(l);
    for (int i = l; i < r+1; i++){
        allQ += isQNum(value);
        value += i+1;   
    }

    cout << allQ << endl;
    
}

正确的代码（100%）

/*
    网易 iOS 编程题-被3整除
    
    有趣的数列：1 12 123 1234 ... 123456789 12345678910 ...
    
    被3整除的规律：FTTFTTFTT...FTT...
    其中 F 为不能被3整除，T 为能被3整除
*/

#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
    
    int l, r;
    int sum = 0;
    cin >> l >> r;
    
    while(l%3!=1) {
        sum++;
        l++;
    }
    while(r%3!=1)
    {
        sum++;
        r--;
    }
    
    cout << (r-l)/3*2+sum << endl;
    
    return 0;
}