首页 > 代码库 > UVA136 求第1500个丑数
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\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就要跑非常久。。
gg
事实上还没法证明检验条件是否正确
然后我们发现。。丑数可以由已有的丑数再加上丑数*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。。跑死你个智障。。。
UVA136 求第1500个丑数