COMDIV - Number of common divisors
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
Albert Chen:
2011-11-28 20:17:32
************Warning***********
|
|
Hazem:
2011-11-09 22:48:15
i use
|
|
??????????????:
2011-11-08 07:22:52
when checking upto (min(a,b))/2 TLE is coming.plz.somebody help me |
|
ontole:
2011-10-31 16:43:33
sqrt(min(a,b)) is giving tle!!! |
|
Yasser Kamel:
2011-10-06 16:49:29
i spend a day for this :
|
|
sri:
2011-10-05 19:47:39
O(sqrt(min(x,y)) is getting TLE???
|
|
Dante is not a Geek:
2011-07-13 14:11:10
Can you give a test case where my code fails? I do not understand why there can be overflow for such small numbers. Submission ID: 5374241 Last edit: 2011-07-14 01:10:56 |
|
Psycho:
2011-06-27 16:46:07
@radhakrishnan u r comparing it wit finding prime which can be done in (sqrt(n)) but here, I think its solution requires at least O(min(x,y)) time correct me if i am wrong |
|
Egor:
2011-06-27 16:46:07
Solution with 0(n/2 + lnln(n)) is ok on pascal =)
|
|
Prateek Khandelwal:
2011-06-27 16:46:07
this is for sir Mir Wasi Ahmed,if you will take 10^6 test cases and each test case is "10^6 10^6" then the code i have submitted which is accepted by you will give tle but for your test cases my code is accepted..
|
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 |