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
|
arp_ee:
2014-06-09 20:28:28
nice question..learnt a new thing. |
|
[Lakshman]:
2014-03-29 10:16:11
Now on TOP. |
|
|
[Lakshman]:
2014-03-29 06:37:44
@Hassan Azzam You are getting TLE not because of scanf or printf it is your naive algo.the worst case complexity is O(sqrt(gcd(a,b))). Last edit: 2014-03-29 06:38:00 |
|
Hassan Azzam:
2014-03-29 00:21:27
problem needs to be burnt -_-
|
|
Bharath Reddy:
2014-03-28 09:35:55
cin and cout gives TLE.
|
|
siddhant gupta:
2014-01-23 13:17:53
do not use cin or cout. it wil give tle. wasted my 2 hrs on such a easy ques.
|
|
I am back:
2014-01-10 17:55:09
easy one AC in first attempt |
|
Vipul Pandey:
2014-01-04 20:53:54
Got AC in 1st attempt! Easy one! took only 15 minutes. |
|
Archangel:
2013-12-25 05:16:11
i am getting WA pls help someone
|
|
Himanshu:
2013-10-17 17:53:24
simple mathematics |
| 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