Pages

Sunday 5 January 2014

Hacker Rank - Unfriendly Numbers

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static int unfriendlyNumbers(long[] a,long k) {
        LinkedList<Long> factors=new LinkedList<Long>();
        for(long i=2;i<=Math.sqrt(k);i++){
            if(k%i==0){
                factors.add(i);
                if(k/i !=i){
                    factors.add(k/i);
                }
            }
        }
        HashSet<Long> hs=new HashSet<Long>();
        for(int i=0;i<a.length;i++){
               hs.add(gcd(a[i], k));
        }
        factors.add(k);
        int counter=0;
        while(!factors.isEmpty()){
            long div=factors.remove();
            boolean flag=true;
            for(long key: hs){
                if(key%div==0){
                    flag=false;
                }
            }
            if(flag){
                counter++;
            }
        }
        return counter;
    }
   
    public static long gcd(long x,long y){
        if(y==0)
            return x;
        return gcd(y, x%y);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        long n=Long.parseLong(st.nextToken()),k=Long.parseLong(st.nextToken());
        st=new StringTokenizer(br.readLine());
        long[]arr=new long[st.countTokens()];
        for(int i=0;i<arr.length;i++){
            arr[i]=Long.parseLong(st.nextToken());
        }
        System.out.println(unfriendlyNumbers(arr, k));
    }
}