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
|
[Lakshman]:
2015-03-10 06:15:02
@Muhammad Annaqeeb: When pyramid cluster was functional the time limit was 6s now the problem has been moved to CUBE cluster, time limit is reduced to 0.6s. As CUBE is 20x times faster than Pyramid. So O(sqrt(gcd(a,b))) can easily pass, it is also recommended to use scanf & printf. |
|
Muhammad Annaqeeb:
2015-03-09 23:52:17
My sumbmision in C++ was accepted in 2014-04-13 in O(sqrt(gcd(a,b)) , now resubmitting the same submission is TLE. Is the limits now harder than a year ago? Is this on purpose or due to upgrades? can anyone confirm this? Last edit: 2015-03-10 03:50:55 |
|
|
[Lakshman]:
2015-02-25 19:51:18
What about a new problem with better constraints like 10^14.
|
|
deerishi:
2015-02-25 18:13:34
Accepted 0.15s! Easy one if you know the math!! |
|
tyler_durden:
2015-02-12 09:12:35
@abdelkarim my solution is O(sqrt(gcd(a,b))) and passed in 0.5 seconds |
|
jaswin kaur:
2015-02-05 21:37:41
got TLE with cin,cout & for loop
|
|
Ayon Das:
2015-01-11 12:11:17
anyone who has done NDIV this is just a nice variation.. AC in one go :) :) |
|
sarelfeniel:
2014-08-22 22:44:46
Easy problem but I/O is a huge bottleneck. |
|
surayans tiwari(http://bit.ly/1EPzcpv):
2014-07-12 11:56:53
after 5 w.a finally accepted in 1.54 sec :D |
|
Kanav Vats:
2014-07-11 15:08:39
Easy...careless mistake costed me 2 WA :( |
| 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