枚举大范围数据。。暴力检查题目条件
#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就要跑非常久。。
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[]={,,};
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。。跑死你个智障。。。