problem statement::
Code: Select all
#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
int t, n[5], prime[2][1000], pwr[2][100], i, j, r, s, l, ind, u, v, m, k, sqr, q, mid;
scanf("%d", &t);
for(i=1; i<=t; i++)
{
q=1;
scanf("%d %d", &n[0], &n[1]);
for(j=0; j<2; j++)
{
m=0;
memset(pwr[j], 0, sizeof(pwr[j]));
sqr=sqrt(n[j]);
for(k=2; k<=sqr; k++)
{
if(!(n[j]%k))
{
prime[j][m]=k;
while(!(n[j]%k))
{
n[j]/=k;
pwr[j][m]++;
}
m++;
}
sqr=sqrt(n[j]);
}
if(n[j]>1)
{
prime[j][m]=n[j];
pwr[j][m]++;
m++;
}
}
for(r=0; prime[0][r]; r++)
{
ind=1;
u=0;
v=m-1;
while(u<=v && ind)
{
mid=(u+v)/2;
if(prime[0][r]==prime[1][mid])
{
ind=0;
if(pwr[1][mid]<pwr[0][r])q*=(pwr[1][mid]+1);
else q*=(pwr[0][r]+1);
}
else if(prime[0][r]<prime[1][mid])v=mid-1;
else if(prime[0][r]>prime[1][mid])u=mid+1;
}
}
printf("%d\n", q);
}
return 0;
}