以递增顺序打印出2^i*3^j*5^k的前n项。假设当前已经求出第x项,那么第x+1项一定是由前x项中的某项乘2,或乘3,或乘5,得到的大于第x项中最小的那个数,于是我们立即得到一个n^2的算法,代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e4+10;
LL a[MAX];
int main() {
LL p1,p2,p3;
LL n,val;
while(scanf("%lld",&n)==1) {
LL v=0;
a[0]=1;
for(int i=1;i<n;i++) {
LL x=1e18;
for(int j=0;j<=i;j++) {
LL t1=a[j]*2,t2=a[j]*3,t3=a[j]*5;
if(t1>a[i-1])x=min(x,t1);
if(t2>a[i-1])x=min(x,t2);
if(t3>a[i-1])x=min(x,t3);
}
a[i]=x;
}
for(LL i=0;i<n;i++) {
printf("%lld\n",a[i]);
}
}
return 0;
}
下面来进行代码的优化,假设第x是由含前x-1项中的某一项a[p1]和2相乘得到的,要使第x+1项大于第x项,和2相乘的项必定大于a[p1],同理和3或5相乘的项必定大于a[p2]或a[p3],所以我们可以在得出第x项的时候,如果是*2得到第x项那么p1后移(保证下一次和2乘的数比这次的大),同理p2,p3的后移也一样,又由于第n项<=2^n<3^n<5^n,而且每次都有后移,所以p1,p2,p3总的后移次数不会超过3n,所以我们得到了一个O(n)的算法,代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e4+10;
LL a[MAX];
int main() {
LL p1,p2,p3;
LL n,val;
while(scanf("%lld",&n)==1) {
LL v=1;
p1=p2=p3=0; a[0]=1;
for(LL i=1;i<=n;i++) {
while(true) {
val=min(a[p1]*2,min(a[p2]*3,a[p3]*5));
if(a[p1]*2==val) p1++;
else if(a[p2]*3==val) p2++;
else p3++;
if(val>v) break;
}
a[i]=val;
v=val;
}
for(LL i=0;i<n;i++) {
printf("%lld\n",a[i]);
}
}
return 0;
}