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.
First line of input: T (Number of test cases)
In next T lines, each have one pair A B (0 < A, B <= 10^6)
One integer describing number of common divisors between two numbers.
TIP -> use scanf and printf FOR C++ ( sive and smallest prime factor )
used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N).
using linear sieve + prime factorization(logn)time
used precalculation of number of divisors. but got 3 tles for using cin and cout.
*** JAVA TIPS
Used Linear sieve+gcd(a, b) + "ios::sync_with_stdio(false); cin.tie(0)..." but STILL TLE
1. paste this line in main function first- "ios::sync_with_stdio(0);
@starters12 i also implemented the same in java getting tle
used linear sieve+gcd+precompute divisors..still get tle using java
Count divisor between gcd(a,b) in sqrt.