被3整除
被3整除
https://www.nowcoder.com/practice/51dcb4eef6004f6f8f44d927463ad5e8
题目难度：二星
考察点：找规律
简要说明：这是一道找规律的题目，只要我们发现其中的规律，题目也就迎刃而解。
- 分析： 对于这道题来说，我们肯定不能直接从l到r遍历一遍，然后对于每个数判断是否能够被3整除，这样的复杂度太高，因为数据范围是10^9，所以我们考虑找规律，打表如下：
1%3 =====> 1
12%3 =====> 0
123%3 =====> 0
1234%3 =====> 1
12345%3 =====> 0
123456%3 =====> 0
那么我们发现从1开始，每隔3个数就有两个数%3=0，那么从[1,x]区间有多少能被3整除的数呢？答案显然为 f(x)=2*x/3，那么从[1,r]区间中被3整除的个数就等于f(r)-f(l-1)。 - 复杂度：
时间复杂度：O(1)
空间复杂度：O(1) - 代码：
#include <bits/stdc++.h> using namespace std; int f(int x) { return 2*x/3; } int main() { int l, r; while(cin>>l>>r) { cout<<f(r)-f(l-1)<<endl; } return 0; }
查看6道真题和解析
Momenta公司福利 584人发布