Uva 136 丑数

n^2暴力就完事，但是上限要高，不然就算不到对应的1500，刘汝佳的写法更好。

#include <bits/stdc++.h>

using namespace std;

const int maxn=10000;

int cnt=4;

long long a[maxn];

map<long long , int> mp;

int main()

{

    // clock_t start,finish;

    // start=clock();

    a[1]=2;

    a[2]=3;

    a[3]=5;

    int i=1;

    while (cnt<3000) {

        for (int j=1;j<=i;j++) {

            long long tmp=a[i]*a[j];

            if (mp[tmp]==0) {

                mp[tmp]=1;

                a[cnt++]=tmp;

            }

        }

        i++;

    }

    a[0]=1;

    sort(a,a+cnt);

    // for (int i=0;i<20;i++) printf("%lld\n",a[i]);

    printf("The 1500'th ugly number is %lld.\n",a[1499]);

    // finish=clock();

    // printf("%lf\n",(double)(finish-start));

    return 0;

}

巴特西

Uva 136 丑数

最新文章

热门文章