Tuesday, 21 July 2015

COMDIV

Standard

Number of common divisors

Link to the question : COMDIV 

HINT : 

The number of common divisors of two numbers is simply the number of divisors of their gcd.

RECOMMENDED QUESTION :

Try solving this question .

SOURCE CODE :

/* SPOJ - Number Of Common Divisors (COMDIV)
         - Sushant Gupta   */

#include<stdio.h>

int hcf(int n1, int n2)
{
    if(n2>n1)
        return hcf(n2,n1);
    else if (n2!=0)
       return hcf(n2, n1%n2);

    else
       return n1;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c=0,i,h;
        scanf("%d%d",&a,&b);
        h= hcf(a,b);
        for(i=1;i*i<=h;i++)
        {
            if(h%i==0)
                c=c+2;

        }
        i=i-1;
        if(i*i==h)
            c--;
        printf("%d\n",c);

    }
    return 0;
}

2 comments:

  1. Can you please provide a simple explanation for "The number of common divisors of two numbers is simply the number of divisors of their gcd."

    ReplyDelete
    Replies
    1. Sorry for the late reply.
      Lets take an example. We find the common divisors of 24 and 36. Their common divisors are : 1,2,3,4,6,12.
      Do you notice that the highest common divisor of 24 and 36 is 12 and {1,2,3,4,6} are divisors of 12 as well. So our question just breaks down to finding the number of divisors of their gcd.

      Delete