problem
小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整除。
solution
下面自己解法只通过了70%，明显超时了
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<functional>
using namespace std;
int main() {
long long l, r;
cin >> l >> r;
long long t;
long long ans=0;
for (long long i = l; i <= r; i++) {
if (i == l) {
t = 0;
for (long long j = 1; j <= l; j++) {
t = ((t * 10) % 3 + j) % 3;
}
}
else {
t = ((t * 10) % 3 + i) % 3;
}
if (t == 0)
ans++;
}
cout << ans << endl;
return 0;
}
为了不超时，看到数据范围就应该明白，这题不能递推，一是数组开不了这么大，二是递推时间很长。因此只能用数学方法算出来(这就是数据范围给我们做题的提示)。
一个数字n如果可以被3整除，，那么，1, 2, 3, 4, …分别对3取模得到1, 2, 0, 1, 2, 0, …，这个时候再看题中给出的序列，1, 12, 123, 1234, …是不是可以把其中元素分解成，那么可以发现，1, 12, 123, 1234, 12345, …，能被3整除的如下false, true, true, false, true, true, false, …，可以发现这个序列以3为周期，因此，代码就可以写出来了。
以下为正确的代码
#include<iostream>
using namespace std;
int fun(int n){
if(n%3==2){
return 2*(n/3)+1;
}else{
return 2*(n/3);
}
}
int main(){
int nl,nr;
cin>>nl>>nr;
cout<<fun(nr)-fun(nl-1);
}