## 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```

hide comments
 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > ive1010: 2022-02-12 12:05:28 find prime divisors of the gcd(a,b) using seive, hieroph4nt: 2021-08-11 09:51:36 weak test cases i guess! O(T * sqrt(gcd(a, b))) passes the test cases. It should be 10 ^ 6 * 10 ^ 3 in worst case. O(T * log(gcd(a, b))) good approach tho. ishraaq_56789: 2021-06-08 16:08:39 Important - 1 is also considered a factor. It cost me a wrong answer. vipvipul12: 2021-05-19 11:23:29 Use "\n" instead of endl to avoid TLE. akshat_19: 2021-05-11 13:56:15 AC in one go. No scanf,printf used. Complexity-->O(logn + sqrt(n)) daredevil666: 2021-03-24 13:06:02 I got an AC without using scanf and printf princemishra: 2020-10-22 08:21:22 used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N). Last edit: 2020-10-22 08:21:37 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. 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

 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