Poj Solution 2649

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

//* @author  mekarlos@gmail.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        Hashtable< Integer,Integer> table=new Hashtable< Integer,Integer>();
        Hashtable< Integer,Integer> table2=new Hashtable< Integer,Integer>();
               BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        int k=0;
        int n=0;
        int x,c=0,r,temp;
        boolean band;
        ArrayList< Integer> v=new ArrayList< Integer>();
        StringTokenizer t;
       while(stdin.ready()){
           t=new StringTokenizer(stdin.readLine());
            n=new Integer(t.nextToken());
            k=new Integer(t.nextToken());
            table.clear();
            table2.clear();
            v.clear();
            band=true;
            x=k;
            if(x!=0)
            {while(x%2==0){
                x/=2;table.put(2, table.get(2)==null?1:table.get(2)+1);
            }
            c=3;
            while(c<=(Math.sqrt((double)x)+1)){
                if(x%c==0){
                    x/=c;
                    table.put(c, table.get(c)==null?1:table.get(c)+1);
                } else c+=2;
            }
            if(x>1)table.put(x, table.get(x)==null?1:table.get(x)+1);
            }
            
            band=true;
            v=new ArrayList(table.keySet());
            if(k!=0&&n!=0&&k>n)
            for(int i=0;i< v.size();i++){
                c=table.get(v.get(i));

                x=0;
                r=0;
                while(x< c){
                    r++;
                    temp=r*v.get(i);
                    if(temp>n){
                        band=false;
                        break;
                    }
                    if(table2.get(temp)==null){
                        table2.put(temp,temp);
                    }
                    while(table2.get(temp)%v.get(i)==0){
                        table2.put(temp, table2.get(temp)/v.get(i));
                        x++;
                        if(x==c)break;
                    }
                }
                if(!band) break;
            }
            if(n==0&&k!=1) band=false;           
            if(band&&k!=0)System.out.println(k+" divides "+n+"!");
            else System.out.println(k+" does not divide "+n+"!");
        }
    }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

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