UVA136 求第1500个丑数

枚举大范围数据。。暴力检查题目条件

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<int> Prime;
typedef long long ll;
bool isPrime(ll x){
    ll i;
    if(x==1) return false;
    for(i=2;i*i<=x;++i){
        if(x%i==0) return false;
    }
    return true;
}
vector<int> Set;
map<int,int> mp;
int pri[]={2,3,5,6,15,10,30};
bool jud(ll x){
    ll temp=x;
        while(temp!=0&&temp%2==0){
            temp/=2;
        }
        while(temp!=0&&temp%3==0){
            temp/=3;
        }
        while(temp!=0&&temp%5==0){
            temp/=5;
        }
        if(temp!=0){
            if(isPrime(temp)){
                // printf("T %d temp%d
",Set[i],temp);
                return false;
            }
            else{
                if(temp==1) return true;
                for(ll j=2;j*j<=temp;++j){
                    if(temp%j==0){
                        // if(temp<100)
                        // printf("temp%I64d j%I64d
",temp,j);
                        if(isPrime(j)) return false;
                    }
                }
                return true;
            }
        }
        return true;
}
int main(){
    int i,j;
    Set.push_back(1);
    for(i=2;i<10000000;++i){
        if(jud(i)){
            Set.push_back(i);
        }
    }
    sort(Set.begin(),Set.end());
    for(i=0;i<1500;++i){
        printf("%d ",Set[i]);
    }
    printf("
");
    printf("The 1500'th ugly number is %d",180625);
    return 0;
}

事实证明正确答案8e9。。。而这个枚举1e7就要跑非常久。。

事实上还没法证明检验条件是否正确

然后我们发现。。丑数可以由已有的丑数再加上丑数*2,3,5所新生成的丑数。。

但是如果你暴力乘法直接map记录出没出现过的数字。。没出现的话直接push

然后我们发现这样。。会漏掉中间的一些数字。。

但是下一轮操作我发现前面的一组数据

1 2 3 4 5 6 8 9 10 15 25再下一轮会加上12

年轻地认为只要取得足够靠后就能补全。。

事实上。。我后来花了大力气去逼近long long 的最大值来逼近。。

答案还是错的。。

那么我们可以理解为。。还有没补上的数字（如果答案输出格式没有问题的话）

那么怎么做比较稳妥呢？

对于第一个数特殊情况我们在集合S push 1

2,3,5乘一遍

2,3,5

取最小的没有出现过的push2

序列变成了1,2

2,3,5乘法一遍

2：2,4

3:　3,6

5:　5,10

我们在这六个数里取最小的。。

重复以上的步骤。。

最后我们得到的序列就是最小的。。

以后碰到中间缺项的时候。。我们可以用每次只取最小的1个！来完成取出完整的连续序列

其实我本来也是这么想的。。

但是我的写法和想法不是一致的。。这个在以后一定要多检查。。你的语句是否在做你期望的事情

下面贴上代码。。

ps q巨今天说对于PE返回WA。。热身赛测一下空格和回车就好了

对于64位整数。。有的评测机不支持%I64d的话。。可能会返回64个空格

但是现在大部分的评测机应该都支持%lld..

比赛的时候最好测试一下。。。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<ll> S;
map<ll,ll> mp;
int p[]={2,3,5};
int n;
int main(){
    scanf("%d",&n);
    S.push_back(1);
    int i,j,flag=0;
    while(S.size()<n&&!flag){
        int sz=S.size();
        vector<ll> k;
        for(i=0;i<sz&&!flag;++i){
            ll t=S[i];
            for(j=0;j<3;++j){
                if(mp[p[j]*t]==0){
                    k.push_back(p[j]*t);
                }
            }
        }
        sort(k.begin(),k.end());
        S.push_back(k[0]);
        mp[k[0]]++;
    }    
    sort(S.begin(),S.end());
    printf("The 1500'th ugly number is 859963392.");
    return 0;
}

最后的输出是算好的1500th结果。。输入是丑数的规模。。

一开始做这个题还有一个错误的想法。。

我算的答案是用2,3,5,6,20,15,30作为基数去乘以不是质数的数来得到答案。。

但是。。不是质数的数仍然可能含有除了2,3,5以外的质因子

所以我们要把这种数排除掉。。于是就有了大暴力检验的模拟。。

8e9。。跑死你个智障。。。