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==) return false;

    for(i=;i*i<=x;++i){

        if(x%i==) return false;

    }

    return true;

}

vector<int> Set;

map<int,int> mp;

int pri[]={,,,,,,};

bool jud(ll x){

    ll temp=x;

        while(temp!=&&temp%==){

            temp/=;

        }

        while(temp!=&&temp%==){

            temp/=;

        }

        while(temp!=&&temp%==){

            temp/=;

        }

        if(temp!=){

            if(isPrime(temp)){

                // printf("T %d temp%d\n",Set[i],temp);

                return false;

            }

            else{

                if(temp==) return true;

                for(ll j=;j*j<=temp;++j){

                    if(temp%j==){

                        // if(temp<100)

                        // printf("temp%I64d j%I64d\n",temp,j);

                        if(isPrime(j)) return false;

                    }

                }

                return true;

            }

        }

        return true;

}

int main(){

    int i,j;

    Set.push_back();

    for(i=;i<;++i){

        if(jud(i)){

            Set.push_back(i);

        }

    }

    sort(Set.begin(),Set.end());

    for(i=;i<;++i){

        printf("%d ",Set[i]);

    }

    printf("\n");

    printf("The 1500'th ugly number is %d",);

    return ;

}

事实证明正确答案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[]={,,};

int n;

int main(){

    scanf("%d",&n);

    S.push_back();

    int i,j,flag=;

    while(S.size()<n&&!flag){

        int sz=S.size();

        vector<ll> k;

        for(i=;i<sz&&!flag;++i){

            ll t=S[i];

            for(j=;j<;++j){

                if(mp[p[j]*t]==){

                    k.push_back(p[j]*t);

                }

            }

        }

        sort(k.begin(),k.end());

        S.push_back(k[]);

        mp[k[]]++;

    }

    sort(S.begin(),S.end());

    printf("The 1500'th ugly number is 859963392.");

    return ;

}

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

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

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

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

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

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

巴特西

UVA136 求第1500个丑数

最新文章

热门文章