| 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
|
||||||||||||||
|
2024-11-13 16:22:41
guys pls don't spoil solution in comments |
||||||||||||||
|
2024-05-29 21:52:12
Try to solve in O(T* logT) , store divisor count in vector using seive |
||||||||||||||
|
2024-05-17 13:29:29
Weak Test Cases, O(T * Sqrt(gcd(a,b))) shouldn't be passed. |
||||||||||||||
|
2022-08-29 17:23:57
1. ___gcd(a,b) 2. for(i=1;i*i<=gcd;i++) 3. must use scanf, printf otherwise you will get TLE Last edit: 2022-08-29 17:55:37 |
||||||||||||||
|
2022-02-12 12:05:28
find prime divisors of the gcd(a,b) using seive, |
||||||||||||||
|
2021-08-11 09:51:36
weak test cases i guess! O(T * sqrt(gcd(a, b))) passes the test cases. It should be 10 ^ 6 * 10 ^ 3 in worst case. O(T * log(gcd(a, b))) good approach tho. |
||||||||||||||
|
2021-06-08 16:08:39
Important - 1 is also considered a factor. It cost me a wrong answer. |
||||||||||||||
|
2021-05-19 11:23:29
Use "\n" instead of endl to avoid TLE. |
||||||||||||||
|
2021-05-11 13:56:15
AC in one go. No scanf,printf used. Complexity-->O(logn + sqrt(n)) |
||||||||||||||
|
2021-03-24 13:06:02
I got an AC without using scanf and printf |
||||||||||||||
RSS