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
tle_infinite1: 2022-08-29 17:23:57

1. ___gcd(a,b)
2. for(i=1;i*i<=gcd;i++)
3. must use scanf, printf otherwise you will get TLE

Last edit: 2022-08-29 17:55:37
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


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