## 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:
3100000 10000012 24747794 238336```
```Output:
3662```

 < 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