学步园

 本题要求写出前1500个仅能被2，3，5整除的数。
最初的想法是从1开始检验该数是否只能被2，3，5整除，方法是这样的，对于一个数，如果它能被2整除，就除以二，如果它能被3整除，就除以三，如果它能被5整除，就除以五，直到不能被2，3，5整除，看结果是不是1，如果是1就满足条件，否则不满足条件。但是第1500个数大约近10亿，显然是1s内不可以完成的。

//1338 Time Limit Exceeded<br /> #include <iostream><br /> #include <vector><br /> using namespace std;</p> <p>vector<__int64> v;</p> <p>void fun()<br /> {<br /> __int64 a,j=6;<br /> int k,sum=5;<br /> v.push_back(1);<br /> v.push_back(2);<br /> v.push_back(3);<br /> v.push_back(4);<br /> v.push_back(5);<br /> while (1)<br /> {<br /> a=j;<br /> while (a!=1)<br /> {<br /> if(a%90==0)<br /> {<br /> a=a/90;<br /> continue;<br /> }<br /> if(a%60==0)<br /> {<br /> a=a/60;<br /> continue;<br /> }<br /> if(a%45==0)<br /> {<br /> a=a/45;<br /> continue;<br /> }<br /> if(a%30==0)<br /> {<br /> a=a/30;<br /> continue;<br /> }<br /> if(a%20==0)<br /> {<br /> a=a/20;<br /> continue;<br /> }<br /> if(a%18==0)<br /> {<br /> a=a/18;<br /> continue;<br /> }<br /> if(a%15==0)<br /> {<br /> a=a/15;<br /> continue;<br /> }<br /> if(a%12==0)<br /> {<br /> a=a/12;<br /> continue;<br /> }<br /> if(a%10==0)<br /> {<br /> a=a/10;<br /> continue;<br /> }<br /> if(a%6==0)<br /> {<br /> a=a/6;<br /> continue;<br /> }<br /> if(a%5==0)<br /> {<br /> a=a/5;<br /> continue;<br /> }<br /> if(a%3==0)<br /> {<br /> a=a/3;<br /> continue;<br /> }<br /> if(a%2==0)<br /> {<br /> a=a/2;<br /> continue;<br /> }<br /> break;<br /> }<br /> if(a==1)<br /> {<br /> v.push_back(j);</p> <p> sum++;<br /> cout<<sum<<" "<<j<<endl;<br /> if(sum==1500)<br /> break;<br /> }<br /> j++;<br /> }<br /> }</p> <p>int main()<br /> {<br /> int n;<br /> fun();<br /> freopen("1338.txt","r",stdin);<br /> cin>>n;<br /> while (n!=0)<br /> {<br /> cout<<v[n-1]<<endl;<br /> cin>>n;<br /> }<br /> fclose(stdin);<br /> return 0;<br /> }
满足条件的数是2^x*3^y*5^z,可以转换为这样的定义，定义一个集合，该集合中有元素1，如果x在集合中，那么2x，3x，5x也在集合中，其它数不再集合中。我们可以定义一个bool数组，初始化为false，从1开始设置为true，如果x为true，则2x，3x，5x设置为true，直到获得1500个true即可，典型的空间换时间的做法，但是这个空间也太大了！这个数组要开到近10亿才可以，显然是不可行的，内存用完了，可能都不够用。
顺着这个思路继续想下去，定义一个集合，该集合中有元素1，如果x在集合中，那么2x，3x，5x也在集合中，其它数不再集合中。按照这个思路走下去：
1
*2
*3
*5
从1*2 3 5中选一个最小的2放入到集合中，然后划掉*2,在2上加入*2
1    2
*3   *2
*5
从1*3 2*2中选一个最小的3放入到集合中，然后划掉1*3,在3上加入*2
1    2    3
*5   *2   *2
从1*5 2*2 3*2中选一个最小的4放入到集合中，然后划掉2*2,,加入2*3,在4上加入*2
1    2    3    4
*5   *3   *2   *2
从1*5 2*2 3*2 4*2中选一个最小的5放入到集合中，然后划掉1*5,加入5*2
2    3     4    5
*3   *2    *2   *2
从1*5 2*2 3*2中选一个最小的6放入到集合中，然后划掉2*3, 3*2,加入2*4 3*3 在6上加入*2
2    3     4     5     6
*4   *3    *2    *2    *2
以此类推，获得1500个数为止。
//1338 Accepted 160K 0MS C++ 476B<br /> #include <iostream><br /> using namespace std;</p> <p>int main()<br /> {<br /> long s[1501] ,p[3]={2,3,5},val[3],pos[3],k,n;<br /> //freopen("1338.txt","r",stdin);<br /> memset(s,0,sizeof(s));<br /> s[0]=1; pos[0]=pos[1]=pos[2]=0;<br /> for(int i=0;i<3;++i)<br /> val[i]=p[i];<br /> for(int i=1;i<=1500;++i)<br /> {<br /> k = val[0]>val[1] ? 1 : 0 ;<br /> k = val[k]>val[2] ? 2 : k ;<br /> if( s[i-1]!=val[k] )<br /> s[i] = val[k] ;<br /> else<br /> --i;<br /> val[k]=p[k]*s[++pos[k]];<br /> }<br /> while(cin>>n&&n)<br /> {<br /> cout<<s[--n]<<endl;<br /> }<br /> //fclose(stdin);<br /> return 0;<br /> }