Poj Solution 3307

http://poj.org/problem?id=3307

//* @author 
import java.util.*;
public class Main{
  public static void main(String args[]){
  
    int k,n;
    Scanner in=new Scanner(System.in);
    k=in.nextInt();
    init();
    while(k-->0){
        n=in.nextInt();
       System.out.printf("%dn",s[n]);
    }
   
   }

  static int MAX=80000;
  static long s[]=new long[MAX];       //���ڴ洢�������
  static long d2[]=new long[MAX];     //�洢���к���������2�ҷ���������
  static long d3[]=new long[MAX];     //�洢���к���������3�ҷ���������
  static long d5[]=new long[MAX];
  static long d7[]=new long[MAX];

  public static void init(){
    int i;
    int pos2,pos3,pos5,pos7;
    long a,b;
    s[1]=1;
    pos2=pos3=pos5=pos7=1;
    for(i=1;i< MAX-1;i++){
        d2[i]=s[i]*2;
        d3[i]=s[i]*3;
        d5[i]=s[i]*5;
        d7[i]=s[i]*7;
        while(d2[pos2]<=s[i])pos2++;     //��������С��s[i]����ô��һ���Ѿ���s[i]�У�����ȥ��
        while(d3[pos3]<=s[i])pos3++;     //��Ȼs[i]�Ǵ��ĸ������д�С����ѡ��4�ģ�
        while(d5[pos5]<=s[i])pos5++;     //�����������һ������ȷ��
        while(d7[pos7]<=s[i])pos7++;
        a=d2[pos2]< d3[pos3]?d2[pos2]:d3[pos3];
        b=d5[pos5]< d7[pos7]?d5[pos5]:d7[pos7];
        s[i+1]=a< b?a:b;
    }
  }
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *