SPOJ.com - Problem 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.

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

One integer describing number of common divisors between two numbers.

Input:
3
100000 100000
12 24
747794 238336

Output:
36
6
2

< Previous 2 3 4 5 6 7 8 9 10 11 12 Next >

	nonushikhar: 2016-01-23 22:01:40 easy ac in one go :)
	dwij28: 2016-01-10 11:44:05 Woo.. Fast input too takes 0.36 seconds.. O(sqrt(gcd(a, b)) using the std::__gcd available in C++.. Any hint on how to make it faster ?? Last edit: 2016-01-11 17:06:33
	ragwave: 2016-01-02 21:45:32 std::__gcd(n,k) under <algorithm> ...can be used to get gcd without defining any function!
	xpshekhar: 2015-12-25 16:13:13 tle in c ac in c++ strange :(
	mdsharique: 2015-12-21 07:59:47 atlast AC after several TLE
	Prateek Agarwal: 2015-12-12 14:34:40 Very Tight Time limit. AC in c++ but TLE in python. Anyone whose result passed in python?
	ram_1897: 2015-09-25 09:21:26 use euclidean algorithm to compute gcd :)
	Abdulsalam Abdo Helal: 2015-09-15 14:30:30 scanf and prinf is recommended to pass time
	Abishek: 2015-09-10 10:00:03 fast i/o and basic math !
	Medo: 2015-08-20 16:03:11 If you are sure of your complexity. Change to Printf scanf, and make sure all your variables are declared as int not long long.