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 5 6 7 8 9 10 11 12 13 14 15 Next >

	Vladimir Kirichenkoff: 2011-06-27 16:46:07 Yes
	Seshadri R: 2011-06-27 16:46:07 Should 1 be always counted as one of the common divisors for the given pair?
	[Retired]: 2011-06-27 16:46:07 TLE
	:D: 2011-06-27 16:46:07 "will O(sqrt (min(x,y) ) pass?" It's pretty unlikely.
	Radhakrishnan Venkataramani: 2011-06-27 16:46:07 will O(sqrt (min(x,y) ) pass?
	Mir Wasi Ahmed: 2011-06-27 16:46:07 @purav: Many solutions including mine used only scanf and got Accepted. So people should not assume that they need fast IO. Sorry to People using some of the slower languages. It seem there is no way I can set different time-limits for different languages. Last edit: 2010-11-03 14:39:15
	purav: 2011-06-27 16:46:07 i got TLE with scanf, had to use faster I/O to get acc
	:(){ :\|: & };:: 2011-06-27 16:46:07 Nice test cases, I got few WA since I was too lame to check for integer overflows ;-)
	numerix: 2011-06-27 16:46:07 Problem is easy to solve, but very I/O related. Absolutely impossible with Python (6 s are not enough for I/O without any calculation!) and even a Pascal solution has to be well optimized to get AC.
	Mir Wasi Ahmed: 2011-06-27 16:46:07 @A. Muh. Primabudi: Sorry, At first I uploaded a test data different from the original one by mistake. Now I replaced the data and re-judged every solution. Sorry for the inconvenience.