Description
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. Software engineer Ivan likes to work. So much that a perfect day for him is when he could spend the whole day until late at night in his corner office, without being distracted from writing code for all sorts of extraneous matter. The only pity is his supervisors do not strongly support him in this, all the time making him participate in all sorts of conversations and presentations.From the first of January of the new year throughout the organization, it was decided to introduce a new order of the staff reporting to the supervisors. Every second day, each engineer should report to his immediate supervisor. Of the remaining days, every third day — to the head of his supervisor. Of the remaining days, every fourth day — to the head of the head of his supervisor. And so on. The organization is very large, so it can be assumed that for ordinary engineers there is an infinite number of levels of supervising. Ivan is not happy about all this bureaucracy, but he needs to learn to live with it. In particular, Ivan needs to plan his vacation so that it would include as many reporting days as possible and as little days, when he can work quietly, as possible. Ivan wants to count how many quiet days will be during his scheduled vacation in order to, possibly, move it to another time.Input
The first line contains integers l and r that are the numbers of the first and the last scheduled days of Ivan’s vacation, counting from the day of introduction of the new order in the company (1 ≤l ≤r ≤ 10 9).Output
Output the number of quiet days during scheduled vacation.Sample Input
| input | output |
|---|---|
1 10 |
3 |
Notes
On the days with numbers 2, 4, 6, 8 and 10 Ivan will report to his immediate supervisor. In the day 5 — to the head of his supervisor, in the day 9 — to the head of the head of his supervisor. The days with numbers 1, 3 and 7 are quiet.Source
http://acm.hust.edu.cn/vjudge/contest/122043#problem/BMy Solution
读懂题意很重要嘿嘿， 就是先每个1个数删去一个数， 然后 在剩余的数字里 每隔2个数删除一个数， 然后又在剩余的数里每隔3个数删除一个数， 一次类推反正笔者自己觉得这个题挺有意思的，嘿嘿^_^#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 1e9 + 8;
bool m[maxn];
int main()
{
#ifdef LOCAL
freopen("a.txt", "r", stdin);
//freopen("b.txt", "w", stdout);
int T = 1;
while(T--){
#endif // LOCAL
int cnt, r, l;
scanf("%d%d", &l, &r);
int x = 2;
while(r/x){
r = r - r/x;
x++;
}
x = 2;
l--;
while(l/x){
l = l - l/x;
x++;
}
printf("%d", r - l);
#ifdef LOCAL
printf("\n");
}
#endif // LOCAL
return 0;
}
Thank you! ------from ProLights