不知道怎么搞的就报名了蓝桥杯，还报的B组的。。。
然后就开始刷刷历年的题目，结果发现题目、数据巨坑。 数据是怎么乱搞都能得个75。。。
这题幸运数测试数据也是太水了，以至于暴力的通通能过，目测题目最大数据也就是10^4+ 不超过10^5
本来想水水就算了的，但是不解为什么锦囊说用堆写。。。想了几天堆的解法，发现有点不好搞，但是用线段树就可以很好的解决了，因为考研很久没写过代码了，复习复习线段树就敲了下。。。
复杂度O(nlog(n)) ,线段树写的比较搓，常数有点大，提交800+ms飘过。
如果用题目给的n为上界，那么就直接0ms飘过了。
解法懂线段树的应该想想就能想的到。
历届试题 幸运数 时间限制：1.0s 内存限制：256.0MB 问题描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。 首先从1开始写出自然数1,2,3,4,5,6,.... 1 就是第一个幸运数。 我们从2这个数开始。把所有序号能被2整除的项删除，变为： 1 _ 3 _ 5 _ 7 _ 9 .... 把它们缩紧，重新记序，为： 1 3 5 7 9 .... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ... 此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...) 最后剩下的序列类似： 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ... 输入格式 输入两个正整数m n, 用空格分开 (m < n < 1000*1000) 输出格式 程序输出 位于m和n之间的幸运数的个数（不包含m和n）。 样例输入1 1 20 样例输出1 5 样例输入2 30 69 样例输出2 8
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <algorithm> 6 using namespace std; 7 #define N 1000010 8 9 //来一发线段树 10 int n,m; 11 int l[4*N],r[4*N],mi[4*N],flag[4*N],pos[4*N];//pos用来记录区间最小值得位置 12 int save[N]; 13 int mipos; 14 15 16 void down(int s) 17 { 18 flag[2*s]+=flag[s]; 19 mi[2*s]-=flag[s]; 20 21 flag[2*s+1]+=flag[s]; 22 mi[2*s+1]-=flag[s]; 23 24 flag[s]=0; 25 } 26 27 void up(int s) 28 { 29 if(mi[2*s]<=mi[2*s+1]) pos[s]=pos[2*s]; 30 else pos[s]=pos[2*s+1]; 31 mi[s]=min(mi[2*s],mi[2*s+1]); 32 } 33 34 void build(int tl,int tr,int s) 35 { 36 l[s]=tl; r[s]=tr; 37 if(tl==tr) 38 { 39 flag[s]=0;//没有标记 40 mi[s]=1111111; 41 pos[s]=tl; 42 return ; 43 } 44 int mid=(tl+tr)/2; 45 build(tl,mid,2*s); 46 build(mid+1,tr,2*s+1); 47 up(s); 48 } 49 50 51 void modify(int id,int num,int s) 52 { 53 if(l[s]==id&&r[s]==id) 54 { 55 mi[s]=num; 56 flag[s]=0; 57 return ; 58 } 59 if(flag[s]!=0) 60 { 61 down(s); 62 } 63 int mid=(l[s]+r[s])/2; 64 if(id<=mid) modify(id,num,2*s); 65 else modify(id,num,2*s+1); 66 up(s); 67 } 68 69 int query(int tl,int tr,int s) 70 { 71 if(l[s]==tl&&tr==r[s]) 72 { 73 //不能在这里搞，要在下一个弄,因为这个时候你不知道最小值是那个 74 return mi[s]; 75 } 76 if(flag[s]!=0) down(s); 77 int mid=(l[s]+r[s])/2; 78 if(tr<=mid) return query(tl,tr,2*s); 79 else if(tl>mid) return query(tl,tr,2*s+1); 80 else{ 81 return min(query(tl,mid,2*s),query(mid+1,tr,2*s+1)); 82 } 83 } 84 85 void allsub(int tl,int tr,int s) 86 { 87 if(l[s]==tl&&r[s]==tr) 88 { 89 flag[s]++; 90 mi[s]--; 91 return ; 92 } 93 if(flag[s]!=0) down(s); 94 int mid=(l[s]+r[s])/2; 95 if(tr<=mid) allsub(tl,tr,2*s); 96 else if(tl>mid) allsub(tl,tr,2*s+1); 97 else 98 { 99 allsub(tl,mid,2*s); 100 allsub(mid+1,tr,2*s+1); 101 } 102 up(s); 103 } 104 105 //这个可以弄掉去 106 /* 107 void findmi(int tl,int tr,int num,int s) 108 { 109 if(l[s]==r[s]) 110 { 111 //现在找到位置了，然后修改就行了 112 modify(l[s],save[l[s]],1); 113 if(l[s]!=1) allsub(1,l[s]-1,1); 114 return ; 115 } 116 if(flag[s]!=0) down(s); 117 int mid=(l[s]+r[s])/2; 118 if(tr<=mid) findmi(tl,tr,num,2*s); 119 else if(tl>mid) findmi(tl,tr,num,2*s+1); 120 else 121 { 122 //负责度有点问题啊，我操！ 123 if( query(tl,mid,1) == num) findmi(tl,mid,num,2*s); 124 else findmi(mid+1,tr,num,2*s+1); 125 } 126 } 127 */ 128 129 void findmi(int tl,int tr,int num,int s) 130 { 131 if(l[s]==tl&&tr==r[s]) 132 { 133 if(mi[s]==num) mipos=min(mipos,pos[s]); 134 return ; 135 } 136 if(flag[s]!=0) down(s); 137 int mid=(l[s]+r[s])/2; 138 if(tr<=mid) findmi(tl,tr,num,2*s); 139 else if(tl>mid) findmi(tl,tr,num,2*s+1); 140 else{ 141 findmi(tl,mid,num,2*s); 142 findmi(mid+1,tr,num,2*s+1); 143 } 144 } 145 146 int main() 147 { 148 //scanf("%d%d",&n,&m); 149 build(1,1000000,1); 150 int cnt=0; 151 152 save[++cnt]=2; 153 modify(cnt,2,1); 154 for(int i=3;i<=1000000;i++) 155 { 156 //应该是从3开始 157 158 int tmi=query(1,cnt,1); 159 if(tmi==1) //说明发现了一个行的 160 { 161 mipos=1111111; 162 //找出一个为1的最小的,并修改 163 findmi(1,cnt,tmi,1); 164 modify(mipos,save[mipos],1); 165 if(mipos!=1) allsub(1,mipos-1,1); 166 }else //得到一个幸运数 167 { 168 //现有的全部减1 169 allsub(1,cnt,1); 170 save[++cnt]=i; 171 modify(cnt,i-cnt,1); 172 } 173 } 174 //速度太慢有待改进 175 176 int n,m; 177 scanf("%d%d",&n,&m); 178 int ans=0; 179 for(int i=1;i<=cnt;i++) 180 { 181 if(save[i]<m&&save[i]>n) ans++; 182 } 183 printf("%d\n",ans); 184 return 0; 185 }