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
|
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..
|
|
Vladimir Kirichenkoff:
2011-06-27 16:46:07
Yes |
|
Seshadri R:
2011-06-27 16:46:07
Should 1 be always counted as one of the common divisors for the given pair? |
|
[Retired]:
2011-06-27 16:46:07
TLE |
|
:D:
2011-06-27 16:46:07
"will O(sqrt (min(x,y) ) pass?"
|
|
Radhakrishnan Venkataramani:
2011-06-27 16:46:07
will O(sqrt (min(x,y) )
|
|
Mir Wasi Ahmed:
2011-06-27 16:46:07
@purav: Many solutions including mine used only scanf and got Accepted. So people should not assume that they need fast IO.
|
|
purav:
2011-06-27 16:46:07
i got TLE with scanf, had to use faster I/O to get acc |
| 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