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.

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

One integer describing number of common divisors between two numbers.

Input:
3
100000 100000
12 24
747794 238336

Output:
36
6
2

< Previous 4 5 6 7 8 9 10 11 12 13 14 Next >

	Muhammad Annaqeeb: 2015-03-09 23:52:17 My sumbmision in C++ was accepted in 2014-04-13 in O(sqrt(gcd(a,b)) , now resubmitting the same submission is TLE. Is the limits now harder than a year ago? Is this on purpose or due to upgrades? can anyone confirm this? Last edit: 2015-03-10 03:50:55
	[Lakshman]: 2015-02-25 19:51:18 What about a new problem with better constraints like 10^14. (Francky) => There's yet a very recent problem with similar method and constraints. So no. (Lakshman)-->Okay No problem. Last edit: 2015-02-26 04:05:21
	deerishi: 2015-02-25 18:13:34 Accepted 0.15s! Easy one if you know the math!!
	tyler_durden: 2015-02-12 09:12:35 @abdelkarim my solution is O(sqrt(gcd(a,b))) and passed in 0.5 seconds
	jaswin kaur: 2015-02-05 21:37:41 got TLE with cin,cout & for loop AC with printf,scanf & while loop whyyy?? Last edit: 2015-06-24 06:09:04
	Ayon Das: 2015-01-11 12:11:17 anyone who has done NDIV this is just a nice variation.. AC in one go :) :)
	sarelfeniel: 2014-08-22 22:44:46 Easy problem but I/O is a huge bottleneck.
	surayans tiwari(http://bit.ly/1EPzcpv): 2014-07-12 11:56:53 after 5 w.a finally accepted in 1.54 sec :D
	Kanav Vats: 2014-07-11 15:08:39 Easy...careless mistake costed me 2 WA :(
	Branimir Rièko: 2014-06-22 18:00:38 Is 0 a divisor?? :)