Wrong Answer in interview street challenge

Question

First of all a small clarification.I did got AC in this problem,but my better approach (which is mathematically equivalent,I assume to my AC solution) is getting a WA verdict There is a problem in interviewstreet which goes like this:

There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.

Input Format:

The first line of input contains two numbers N and K seperated by spaces. N is the number of unfriendly numbers, K is the friendly number. The second line of input contains N space separated unfriendly numbers.

Output Format:

Output the answer in a single line.

Sample Input:

8 16
2 5 7 4 3 8 3 18

Sample Output:

1

Explanation:

Divisors of the given friendly number 16, are { 1, 2, 4, 8, 16 } and the unfriendly numbers are { 2, 5, 7, 4, 3, 8, 3, 18 }. Now 1 divides all unfriendly numbers, 2 divides 2, 4 divides 4, 8 divides 8, but 16 divides none of them. So only one number exists which divides the friendly number but does not divide any of the unfriendly numbers. So the answer is 1.

My Algo (which got AC) is as follows:

1. Let the possible unfriendly numbers be input[i] where 0<=i

2. For each input[i] find gcd(input[i],k).

3. Store all factors of gcd(input[i],k) for all i in range (0,n) in a set.Lets call this set PossibleFactors.

4. For each factor of k,check whether it divides any of the element in PossibleFactor. If no then increase count of answwer

I modified the algo assuming the following:

Instead of storing all factors of gcd(input[i],k) in a set , find out the lcm of gcd(input[i],k) for all i in range (0,n). This can easily be done by the following LOC

lcm = (lcm/gcd(gcd(input[i],k),lcm))*(gcd(input[i],k))

Now for all factors of k check whether they divide the lcm. If no then increase count.

However this assumption is giving me WA. Is it because of any flaw in my logic? If yes please point out (if possible with a mathematical proof) of how the two approaches differ?

Here is my code with the second approach for reference (and possible bugs)

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef long long LL;
LL gcd(LL a,LL b) {
    LL c;
    while(b) {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int main()
{
    long long int n,k,i,x,j,ans=0,a,num,g;
    scanf("%lld%lld",&n,&k);
    num=1;
    for(i=0;i<n;i++) {
        scanf("%lld",&a);
        g=gcd(a,k);
        num=(num/gcd(num,g))*g;
    }
    x=sqrt(k);ans=0;
    for(i=1;i<=x;i++) {
        if(!(k%i)) {
            if((num%i)) ans++;
            if((k/i != i) && (num%(k/i))) ans++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Answer 1

You say “find out the lcm of gcd(input[i],k) for all i in range (0,n) ... Now for all factors of k check whether they divide the lcm. If no then increase count.”

There is a flaw in that method. Consider the case of k=20, U=[12,25,30]. Then GCDs = [4,5,10] and LCM = 20. So all factors of k divide LCM, leading to a zero count by the quoted criterion. But k itself does not divide any of the U, so count should be 1 instead of 0.