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.


First line of input: T (Number of test cases)
In next T lines, each have one pair A B (0 < A, B <= 10^6)


One integer describing number of common divisors between two numbers.


100000 100000
12 24
747794 238336

hide comments
naman_mawandia: 2019-12-29 20:42:46

use printf & scanf instead of cout & cin, costed me 2 TLE

Last edit: 2019-12-29 20:43:54
mrmajumder: 2019-11-30 06:54:04

The trick here is that, the divisors of the gcd(a, b) is the answer [Let a, b be the given pair].
I did sieving to find prime numbers. Used those primes to prime factorize the value of the gcd. Then counted the number of divisors possible.
Use optimized I/O, unless there will be casualties.

rana_1234: 2019-10-29 20:56:00

cout gave me accepted and printf gave me WA. :)

importme: 2019-09-28 21:42:38

My 50th on SPOJ!!

sanket17: 2019-07-13 06:42:47

if u r using cin and cout then copy this lines

towhid1zaman: 2019-06-19 06:10:26

find gcd, and dont use printf

frochbg: 2019-05-30 20:07:31

Nice problem :)

scolar_fuad: 2019-04-13 15:42:27

Only a single cin and cout will cost you TLE don't need to seive just find gcd and then count divisor

happy coding

Muhammad Annaqeeb: 2019-04-09 17:54:13

Here is a note about comparing the same solution speed across different programming languages:
C++ with non-optimized cin and cout ---Time Limit Exceeded
C++ with optimized cin and cout -- 0.32 second
Java with non-optimized IO -- Time Limit Exceeded
Java with optimized IO -- 0.52 second
Free Pascal with non-optimized IO -- 0.34 second

suraj1611: 2019-03-18 19:48:13

using scanf and printf instead of cin and cout could help!

Added by:Mir Wasi Ahmed
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