| 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
|
||||||||||||||
|
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). Last edit: 2020-10-22 08:21:37 |
||||||||||||||
|
2020-06-04 08:47:25
used precalculation of number of divisors. but got 3 tles for using cin and cout. use scanf and printf to avoid tle. |
||||||||||||||
|
2020-04-30 15:50:54
1. paste this line in main function first- "ios::sync_with_stdio(0); cin.tie(0);" in main function if you are goind to use cin and cout. 2. just calculate GCD and the count number of divisors of that. Hint:- user sqrt(gcd(a,b)) to calculate number of divisors to be safe from TLE. Thats it..Goog Luck..Nice problem |
||||||||||||||
|
2020-04-29 10:02:37
@starters12 i also implemented the same in java getting tle |
||||||||||||||
|
2020-04-28 01:19:36
Count divisor between gcd(a,b) in sqrt. |
||||||||||||||
|
2020-04-14 11:44:13
If you r using cin or cout then paste this line in main function first- "ios::sync_with_stdio(0); cin.tie(0);" . Secondly if u r using sqrt() function for running in loop, then use floor(sqrt()); if u r doing something like- if(floor(sqrt())*floor(sqrt())==z) else u will get W.A. Last edit: 2020-04-14 12:34:57 |
||||||||||||||
|
2020-04-07 12:46:11
always use scanf and printf for IO operations in spoj questions Most of them gives TLE with cin and cout |
||||||||||||||
|
2019-12-29 20:42:46
use printf & scanf instead of cout & cin, costed me 2 TLE Last edit: 2019-12-29 20:43:54 |
||||||||||||||
|
2019-11-30 06:54:04
The trick here is that, the divisors of the gcd(a, b) is the answer [Let a, b be the given pair]. I did sieving to find prime numbers. Used those primes to prime factorize the value of the gcd. Then counted the number of divisors possible. Use optimized I/O, unless there will be casualties. |
||||||||||||||
|
2019-10-29 20:56:00
cout gave me accepted and printf gave me WA. :) |
||||||||||||||
RSS