COMDIV - Number of common divisors
You will be given T (T ≤ 106) pairs of numbers. All you have to tell is the number of common divisors between the 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 ≤ 106)
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
|
killjee_15:
2016-03-24 19:36:49
sometimes thinking too much is dangerous :( 2 TLEs for too much thinking |
|
ghost_wire:
2016-02-08 19:20:42
easy one for c++
|
|
Govind Lahoti:
2016-01-26 17:36:51
use scanf/printf |
|
nonushikhar:
2016-01-23 22:01:40
easy ac in one go :) |
|
dwij28:
2016-01-10 11:44:05
Woo.. Fast input too takes 0.36 seconds.. O(sqrt(gcd(a, b)) using the std::__gcd available in C++.. Any hint on how to make it faster ?? Last edit: 2016-01-11 17:06:33 |
|
ragwave:
2016-01-02 21:45:32
std::__gcd(n,k) under <algorithm> ...can be used to get gcd without defining any function! |
|
xpshekhar:
2015-12-25 16:13:13
tle in c
|
|
mdsharique:
2015-12-21 07:59:47
atlast AC after several TLE |
|
Prateek Agarwal:
2015-12-12 14:34:40
Very Tight Time limit. AC in c++ but TLE in python.
|
|
ram_1897:
2015-09-25 09:21:26
use euclidean algorithm to compute gcd :) |
| 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 |
RSS