SPOJ.com - Problem COMDIV

COMDIV - Number of common divisors

no tags

You will be given T (T ≤ 10⁶) pairs of numbers. All you have to tell is the number of common divisors between the 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⁶)

Output

One integer describing number of common divisors between two numbers.

Example

Input:
3
100000 100000
12 24
747794 238336

Output:
36
6
2

Submit solution!

hide comments

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

	princemishra: 2020-10-22 08:21:22 used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N). Last edit: 2020-10-22 08:21:37
	md_yasin: 2020-06-04 08:47:25 used precalculation of number of divisors. but got 3 tles for using cin and cout. use scanf and printf to avoid tle.
	landi58: 2020-04-30 15:50:54 1. paste this line in main function first- "ios::sync_with_stdio(0); cin.tie(0);" in main function if you are goind to use cin and cout. 2. just calculate GCD and the count number of divisors of that. Hint:- user sqrt(gcd(a,b)) to calculate number of divisors to be safe from TLE. Thats it..Goog Luck..Nice problem
	vish8062: 2020-04-29 10:02:37 @starters12 i also implemented the same in java getting tle
	symoon: 2020-04-28 01:19:36 Count divisor between gcd(a,b) in sqrt.
	vritta: 2020-04-14 11:44:13 If you r using cin or cout then paste this line in main function first- "ios::sync_with_stdio(0); cin.tie(0);" . Secondly if u r using sqrt() function for running in loop, then use floor(sqrt()); if u r doing something like- if(floor(sqrt())floor(sqrt())==z) else u will get W.A. Last edit: 2020-04-14 12:34:57*
	shivamvermadev: 2020-04-07 12:46:11 always use scanf and printf for IO operations in spoj questions Most of them gives TLE with cin and cout
	naman_mawandia: 2019-12-29 20:42:46 use printf & scanf instead of cout & cin, costed me 2 TLE Last edit: 2019-12-29 20:43:54
	mrmajumder: 2019-11-30 06:54:04 The trick here is that, the divisors of the gcd(a, b) is the answer [Let a, b be the given pair]. I did sieving to find prime numbers. Used those primes to prime factorize the value of the gcd. Then counted the number of divisors possible. Use optimized I/O, unless there will be casualties.
	rana_1234: 2019-10-29 20:56:00 cout gave me accepted and printf gave me WA. :)

Submit solution!

Added by:	Mir Wasi Ahmed
Date:	2010-10-31
Time limit:	0.600s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem, used in UODA TST