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.
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;
}
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."
ReplyDeleteSorry for the late reply.
DeleteLets 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.