| 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
|
||||||||||||||
|
2019-01-11 13:00:54
Just use scanf and printf for I/O , avoid cin & cout in C++ costed me TLE. |
||||||||||||||
|
2018-10-30 08:55:54
What's the application of gcd in this problem?? |
||||||||||||||
|
2018-10-14 17:50:59
AC in 3rd go , just use fast input/output , no need to build sieve , just find factors for every test case in O(sqrt(n)) Last edit: 2018-10-14 17:51:15 |
||||||||||||||
|
2018-08-28 22:04:28
Spoiler Alert! Find the gcd of two numbers and then, number of divisors. Optimise in both the cases along with faster i/o. Last edit: 2018-08-28 22:04:53 |
||||||||||||||
|
2018-08-17 11:11:34
use Fast I/O using better mathematical logic , no need to use scanf printf.. |
||||||||||||||
|
2018-02-20 20:36:06
use scanf and printf , no need to use seive |
||||||||||||||
|
2018-01-02 15:14:00
bhosadi waalo ac in one go ka kya show off krte rehte ho gand utha ke har jagah |
||||||||||||||
|
2018-01-02 14:48:23
AC in 1 go :) |
||||||||||||||
|
2017-12-27 16:39:58
Man , Never thought i would end up with fastest submission till date ( 0.10s ) Fast I/O + sieve_modified + binary_gcd + O( log(N) ) +factorization method for number of divisors got me this :) Last edit: 2017-12-27 20:04:49 |
||||||||||||||
|
2017-12-19 18:25:20
use sieve first then gcd AC in one go:-) |
||||||||||||||
RSS