蓝桥杯2013年第四届真题-幸运数 （C++代码）

解题思路:

         1.思路很简单，就是开个一维数组，模拟手算，作递增1的初始化，形如[1，2，3..n]，注意理解题，因为这里只算位于m 到 n之间的幸运数个数，那算遍历数组，算到n就可以结束了。   

          2.我的算法中没有将删掉的数用后面的数补空位，是因为那样每一轮删除数字，都要对整个数组移位，时间复杂度太高，为O(n*n)，果断超时

          3.因为没有将删除的数用后位数补上，说白了就是没有更新数的的下标。解决办法很简单，就是跳过空位，用step表示数字的实际下标( 姑且叫逻辑下标比较好理解些！ )，更新下标step,满足整除情况时，删掉该位置的数字，即置为0
注意事项:  

           这里代码看起来两重循环 ，好像时间复杂度达到了o(n^2),但稍微想想，时间复杂度实际上是小了很多，

O(n*e),由于计算中，删掉的数字的个数是都是不定的，但可以肯定e是远小于n的

参考代码:

#include<iostream>
#define maxBit 1000050
using namespace std;

int main(){
	int a[maxBit],m,n,count=0,i=2,t;
	cin>>m>>n;	//	m < n <1000000
	if(n-m<=1)
	{    cout<<count; return 0;}   //m n之间没有数时，count为0
	for(int j=1;j<=n;j++)
		a[j]=j;		//初始化数列
	while(i<=n){
		while(a[i]==0)i++;
		int step=0;
			t=a[i];  //a[i]有可能也会被置0，不作除数，用t保存值
		for(int d=1;d<=n;d++){	//相关序号的数 置为0 
			if(a[d]!=0)		step++; //记录逻辑下标
		if(step%t==0&&step!=0)	a[d]=0;   
		}
		if(a[i]!=0) i++;      //如果算完了一轮没有删除a[i],则保留，指针i后移
	}
	for(i=m+1;i<n;i++)
		if(a[i]!=0) count++;
	cout<<count;
		return 0;
}