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
|
anksjain:
2020-12-05 13:13:53
TIP -> use scanf and printf FOR C++ ( sive and smallest prime factor ) |
|
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).
|
|
ridhish_jain:
2020-10-07 19:38:01
using linear sieve + prime factorization(logn)time
|
|
md_yasin:
2020-06-04 08:47:25
used precalculation of number of divisors. but got 3 tles for using cin and cout.
|
|
jyoti369:
2020-05-16 08:34:04
*** JAVA TIPS
|
|
coder_ahmed:
2020-05-15 14:02:52
Used Linear sieve+gcd(a, b) + "ios::sync_with_stdio(false); cin.tie(0)..." but STILL TLE |
|
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 |
|
starters12:
2020-04-29 09:39:31
used linear sieve+gcd+precompute divisors..still get tle using java
|
|
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