不知道怎么搞的就报名了蓝桥杯，还报的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）。样例输入11 20样例输出15样例输入230 69样例输出28

 

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             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     else121     {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             //现有的全部减1169             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]
           
            n) ans++;182 }183 printf("%d\n",ans);184 return 0;185 }