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

symoon: 2020-04-28 01:19:36

Count divisor between gcd(a,b) in sqrt.


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