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

hide comments
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
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


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