Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 可以软打表

Posted by KatrineYang at 2016-09-09 12:57:16 on Problem 1338 and last updated at 2016-09-09 12:59:00
```先苯地暴力计祘一遍最大能到多少（大概用10幾秒吧），就是我代妈里的preprocess()，结果是859963392，然后㞎这个范围内面的2,3,5的幂次列出来再排序即可

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

long long int uglyNum[1505];

void preprocess(){
int cnt = 1;
for(int i = 1; ; i++){
int I = i;
while(I%2==0){
I/=2;
}
while(I%3==0){
I/=3;
}
while(I%5==0){
I/=5;
}
if(I==1){
uglyNum[cnt] = i;
cnt++;
}
//cout << cnt << endl;
if(cnt > 1500) break;
}
}

const int THRES = 859963392;

void preprocess1(){
int cnt = 1;
long long int p2 = 1;
while(1){
long long int p3 = p2;
while(1){
long long int p5 = p3;
while(p5 <= THRES){
//cout << p5 << endl;
uglyNum[cnt] = p5;
cnt++;
p5 *= 5;
}
p3 *= 3;
if(p3 > THRES) break;
}
p2 *= 2;
if(p2 > THRES) break;
}
sort(uglyNum+1, uglyNum+1501);
}

int main() {
preprocess1();
while(1){
int n;
scanf("%d", &n);
if(n == 0) break;
printf("%I64d\n", uglyNum[n]);
}
return 0;
}
```

Followed by: