UVA136 求第1500个丑数-白红宇

UVA136 求第1500个丑数

阅读量：5069 次

发布时间：2019-06-12

本文共 2316 字，大约阅读时间需要 7 分钟。

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;vector
          
            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
           
             Set;map
            
              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\n",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\n",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("\n"); 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 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          using namespace std;typedef long long ll;vector
          
            S;map
           
             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()
            
              k; for(i=0;i