【网易】被3整除

题

https://www.nowcoder.com/practice/51dcb4eef6004f6f8f44d927463ad5e8?tpId=98&tqId=32825&tPage=1&rp=1&ru=/ta/2019test&qru=/ta/2019test/question-ranking

　　题目描述

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

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

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

　　输入描述:

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

　　输出描述:

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

　　示例1

　　输入

2 5

　　输出

　　说明

　　12, 123, 1234, 12345...
　　其中12, 123, 12345能被3整除。

暴力法

　　时间复杂度：O(N)。

　　空间复杂度：O(1)。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int sumOfNumber(int i)
 5 {
 6     int sum = 0;
 7     while (i / 10)
 8     {
 9         int x = i % 10;
10         sum += x;
11         sum %= 3;
12         i /= 10;
13     }
14     sum += i;
15     return sum;
16 }
17 
18 int main()
19 {
20     int l, r;
21     cin >> l >> r;
22     int cnt = 0;
23     for (int i = 1, sum = 0; i <= r; ++i)
24     {
25         sum += sumOfNumber(i);
26         sum %= 3;
27         if (i >= l && sum % 3 == 0)
28             cnt++;
29     }
30     cout << cnt << endl;
31     return 0;
32 }

找规律

　　时间复杂度：O(1)。

　　空间复杂度：O(1)。

　　1、能被3整除的数的数位和是3的倍数；2、这里的数位和实际上是前缀和。

　　对于1到n模3的结果：1,2,0,1,2,0,1,2,0,...，结合前缀和，数列模3的结果：1,0,0,1,0,0,1,0,0,...，即数列中连续3个数中会出现2个被3整除的数。结果为[1, r]个数与[1, l-1]的个数之差。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int l, r;
 7     cin >> l >> r;
 8     l--;
 9     int lcnt = (l / 3) * 2;
10     lcnt += (l % 3 > 1) ? 1 : 0;
11     int rcnt = (r / 3) * 2;
12     rcnt += (r % 3 > 1) ? 1 : 0;
13     cout << (rcnt - lcnt);
14     return 0;
15 }