2010年9月12日日曜日

PKU Judge Online 1338 Ugly Numbers

■1338 Ugly Numbers

□Problem
素因数が2,3,5のみである自然数をugly numberと呼ぶ.n個目のugly numberを表示せよ.

□Solution
n≦1500であるので,先に生成しておけばよい.

□Code(かなり適当です)
package p1338;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

Scanner sc=new Scanner(System.in);

final int INF=Integer.MAX_VALUE;
final double EPS=1e-9;

void run(){
LinkedList<Long> list=new LinkedList<Long>();
long r5=1;
for(int k=0; k<14; k++){
if(r5>1000000000)
break;
long r3=1;
for(int j=0; j<19+1; j++){
if(r5*r3>1000000000)
break;
long r2=1;
for(int i=0; i<31; i++){
if(r2*r3*r5>1000000000)
break;
list.add(r2*r3*r5);
r2*=2;
}
r3*=3;
}
r5*=5;
}
Long[] a=list.toArray(new Long[0]);
sort(a);
for(;;){
int m=sc.nextInt();
if(m==0)
break;
println(a[m-1]+"");
}
}

boolean ugly(int n){
while(n%2==0)
n/=2;
while(n%3==0)
n/=3;
while(n%5==0)
n/=5;
return n==1;
}

void print(String s){
System.out.print(s);
}

void println(String s){
System.out.println(s);
}

public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

0 件のコメント: