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.

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

Submit solution!

hide comments

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

	ridhish_jain: 2020-10-07 19:38:01 using linear sieve + prime factorization(logn)time I did this method, even used scanf printf instead of cin cout.....still giving TLE
	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.
	jyoti369: 2020-05-16 08:34:04 *** JAVA TIPS 1. USE FAST I/O 2. The number of common divisors of two numbers is simply the number of divisors of their gcd. 3.THINK OF YOUR OWN...
	coder_ahmed: 2020-05-15 14:02:52 Used Linear sieve+gcd(a, b) + "ios::sync_with_stdio(false); cin.tie(0)..." but STILL 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
	starters12: 2020-04-29 09:39:31 used linear sieve+gcd+precompute divisors..still get tle using java
	symoon: 2020-04-28 01:19:36 Count divisor between gcd(a,b) in sqrt.
	kabbo25: 2020-04-17 20:14:57 using linear sieve + prime factorization(logn)time
	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*

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