PKU Judge Online 1338 Ugly Numbers

■1338 Ugly Numbers

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

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

□Code(かなり適当です)

view plainprint?

1. package p1338;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.  Scanner sc=new Scanner(System.in);  
14.   
15.  final int INF=Integer.MAX_VALUE;  
16.  final double EPS=1e-9;  
17.   
18.  void run(){  
19.   LinkedList<Long> list=new LinkedList<Long>();  
20.   long r5=1;  
21.   for(int k=0; k<14; k++){  
22.    if(r5>1000000000)  
23.     break;  
24.    long r3=1;  
25.    for(int j=0; j<19+1; j++){  
26.     if(r5*r3>1000000000)  
27.      break;  
28.     long r2=1;  
29.     for(int i=0; i<31; i++){  
30.      if(r2*r3*r5>1000000000)  
31.       break;  
32.      list.add(r2*r3*r5);  
33.      r2*=2;  
34.     }  
35.     r3*=3;  
36.    }  
37.    r5*=5;  
38.   }  
39.   Long[] a=list.toArray(new Long[0]);  
40.   sort(a);  
41.   for(;;){  
42.    int m=sc.nextInt();  
43.    if(m==0)  
44.     break;  
45.    println(a[m-1]+"");  
46.   }  
47.  }  
48.   
49.  boolean ugly(int n){  
50.   while(n%2==0)  
51.    n/=2;  
52.   while(n%3==0)  
53.    n/=3;  
54.   while(n%5==0)  
55.    n/=5;  
56.   return n==1;  
57.  }  
58.   
59.  void print(String s){  
60.   System.out.print(s);  
61.  }  
62.   
63.  void println(String s){  
64.   System.out.println(s);  
65.  }  
66.   
67.  public static void main(String[] args){  
68.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
69.   new Main().run();  
70.  }  
71. }  

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();
 }
}