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
|
hieroph4nt:
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. |
|
ishraaq_56789:
2021-06-08 16:08:39
Important - 1 is also considered a factor. It cost me a wrong answer. |
|
vipvipul12:
2021-05-19 11:23:29
Use "\n" instead of endl to avoid TLE. |
|
akshat_19:
2021-05-11 13:56:15
AC in one go. No scanf,printf used. Complexity-->O(logn + sqrt(n)) |
|
daredevil666:
2021-03-24 13:06:02
I got an AC without using scanf and printf |
|
princemishra:
2020-10-22 08:21:22
used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N).
|
|
md_yasin:
2020-06-04 08:47:25
used precalculation of number of divisors. but got 3 tles for using cin and cout.
|
|
landi58:
2020-04-30 15:50:54
1. paste this line in main function first- "ios::sync_with_stdio(0);
|
|
vish8062:
2020-04-29 10:02:37
@starters12 i also implemented the same in java getting tle |
|
symoon:
2020-04-28 01:19:36
Count divisor between gcd(a,b) in sqrt. |
| 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