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 1 2 3 4 5 6 7 8 9 10 11 Next >

	raghav6: 2019-01-11 13:00:54 Just use scanf and printf for I/O , avoid cin & cout in C++ costed me TLE.
	duet_cse16: 2018-10-30 08:55:54 What's the application of gcd in this problem??
	saketag007: 2018-10-14 17:50:59 AC in 3rd go , just use fast input/output , no need to build sieve , just find factors for every test case in O(sqrt(n)) Last edit: 2018-10-14 17:51:15
	jyotiradityafc: 2018-08-28 22:04:28 Spoiler Alert! Find the gcd of two numbers and then, number of divisors. Optimise in both the cases along with faster i/o. Last edit: 2018-08-28 22:04:53
	puneetgargmnc: 2018-08-17 11:11:34 use Fast I/O using better mathematical logic , no need to use scanf printf..
	srjsunny: 2018-02-20 20:36:06 use scanf and printf , no need to use seive
	viniet_sw: 2018-01-02 15:14:00 bhosadi waalo ac in one go ka kya show off krte rehte ho gand utha ke har jagah
	sanyam19: 2018-01-02 14:48:23 AC in 1 go :)
	karthik1997: 2017-12-27 16:39:58 Man , Never thought i would end up with fastest submission till date ( 0.10s ) Fast I/O + sieve_modified + binary_gcd + O( log(N) ) +factorization method for number of divisors got me this :) Last edit: 2017-12-27 20:04:49
	chetan4060: 2017-12-19 18:25:20 use sieve first then gcd AC in one go:-)