Tuesday 30 June 2015

COMDIV


Number Of Common Divisors

Link to the question: COMDIV

HOW TO APPROACH:

The problem asks us to find the number of common divisors between two numbers. So its very obvious that the number which is formed by the common divisors of both the numbers is their gcd.

  RECOMMENDED QUESTION :

Try this sorting question after this one.

 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;

}

STREETR

STREET TREES 

Link to the question: STREETR

HOW TO APPROACH:

The question asks us to find the minimum number of trees which must be planted so that the distance between the adjacent trees is same. Hence we find the gcd of the difference between the adjacent trees, and then divide the difference with the gcd and it.

RECOMMENDED QUESTION :

Try this very easy question.

SOLUTION :

/* Street Trees (STREETR) */
/* -Susahnt Gupta */

#include<stdio.h>
long long int gcd(long long int a, long long int b)
{
    if(b>a)
        return gcd(b,a);
     else if(b!=0)
            return gcd(b,a%b);
    else
        return a;
}

int main()
{
    int t,i;
    scanf("%d",&t);
    long long int a[t],h,diff,s=0;
    for(i=0;i<t;i++)
        scanf("%lld",&a[i]);
     h= a[1]-a[0];
    for(i=1;i<t;i++)
    {
        diff= a[i]- a[i-1];
        h= gcd(diff,h);
    }

    for(i=1;i<t;i++)
    {
        diff= a[i]- a[i-1];
        s= s+ (diff/h)- 1;
    }
    printf("%lld\n",s);
    return 0;
}