Algorithm

Problem link- https://www.spoj.com/problems/COMDIV/

COMDIV - Number of common divisors

no tags 

 

You will be given T (T<=10^6) pair of numbers. All you have to tell is the number of common divisors between two numbers in each pair.

Input

First line of input: T (Number of test cases)
In next T lines, each have one pair A B (0 < A, B <= 10^6)

Output

One integer describing number of common divisors between two numbers.

Example

Input:
3
100000 100000
12 24
747794 238336

Output:
36
6
2

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <math.h>
#define s(n) scanf("%d",&n)
using namespace std;
int gcd(int a,int b)
{
	if(b==0)
	return a;
	else
	gcd(b,a%b); 
}

int main()
{
	int t;
	s(t);
	while(t--)
	{
		int a,b,c=0;
		s(a);
		s(b);
		c=gcd(a,b);
		int count=0;
		for(int i=1;i<=sqrt(c);i++)
		{
			if(c%i==0)
			{
				count+=2;;
			}
			if(i*i==c)
			count--;
		}
		printf("%d\n",count);
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
100000 100000
12 24
747794 238336

Output

x
–
+
cmd
36
6
2
Advertisements

Demonstration

SPOJ Solution-Number of common divisors-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python