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
anksjain: 2020-12-05 13:13:53

TIP -> use scanf and printf FOR C++ ( sive and smallest prime factor )

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


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