I solved this problem COMDIV on spoj.
and my logic is correct i know...
to find the number of common divisors of 2 number we just need to find the total number of divisors of their gcd.
my code for the same was.-
#include<stdio.h>
#include<math.h>
int gcd(int p,int q);
int gcd(int p,int q)
{
int t;
if(p>q)
{
t=p;
p=q;
q=t;
}
int r;
do
{
r=p%q;
if(r!=0)
{
p=q;
q=r;
}
}while(r!=0);
return q;
}
int nf(int n);
int nf(int n)
{
int i=2,j=0;
while(i<sqrt(n))
{
if(n%i==0)
{
j=j+2;
}
i++;
}
if(i*i==n)
{
j=j+1;
}
j=j+2;
return j;
}
int main()
{
int t,a,b,h;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &a, &b);
if(a==0&&b==0)
printf("0");
else
{
h=gcd(a,b);
printf("%d\n",nf(h));
}
}
return 0;
}
the code runs fine on ideone..but i am getting WA everytime...with java i got TLE.please help me.
Thank You!