蓝桥杯 幸运数

 1 #include <iostream>
 2 using namespace std;
 3 const int MAXN = 1000005;
 4 int a[MAXN], nxt[MAXN];
 5 
 6 int main()
 7 {
 8     int l, r;
 9     cin >> l >> r;
10     for (int i = 1; i <= r / 2; i++) { a[i] = 2 * i - 1; nxt[i] = i + 1; }
11     nxt[r / 2] = -1;
12     for (int k = 0; ; k++)
13     {            
14         int i = 1, tmp = nxt[1], last = 1;
15         int tmp2 = tmp;
16         for (int j = 1; j < k + 1; j++)    tmp2 = nxt[tmp2];
17         int dx = a[tmp2];
18         while (tmp != -1)
19         {
20             if ((i + 1) % dx == 0) nxt[last] = nxt[tmp];
21             last = tmp;
22             tmp = nxt[tmp];
23             i++;
24         }
25         if (dx > i) break;
26     }
27     int tmp = 1, cnt = 0;
28     while (tmp != -1) { if (a[tmp] > l && a[tmp] < r) cnt++; tmp = nxt[tmp]; }
29     cout << cnt << endl;
30     return 0;
31 }