| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||||||||||
|
2016-03-24 19:36:49
sometimes thinking too much is dangerous :( 2 TLEs for too much thinking |
||||||||||||||
|
2016-02-08 19:20:42
easy one for c++ to increase input and output speed try this: ios::sync_with_stdio(false); cin.tie(0); |
||||||||||||||
|
2016-01-26 17:36:51 Govind Lahoti
use scanf/printf |
||||||||||||||
|
2016-01-23 22:01:40
easy ac in one go :) |
||||||||||||||
|
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 |
||||||||||||||
|
2016-01-02 21:45:32
std::__gcd(n,k) under <algorithm> ...can be used to get gcd without defining any function! |
||||||||||||||
|
2015-12-25 16:13:13
tle in c ac in c++ strange :( |
||||||||||||||
|
2015-12-21 07:59:47
atlast AC after several TLE |
||||||||||||||
|
2015-12-12 14:34:40 Prateek Agarwal
Very Tight Time limit. AC in c++ but TLE in python. Anyone whose result passed in python? |
||||||||||||||
|
2015-09-25 09:21:26
use euclidean algorithm to compute gcd :) |
||||||||||||||
RSS