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.
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.
Important - 1 is also considered a factor. It cost me a wrong answer.
Use "\n" instead of endl to avoid TLE.
AC in one go. No scanf,printf used. Complexity-->O(logn + sqrt(n))
I got an AC without using scanf and printf
used gcd and prime factorization with int, scanf , printf and finally got AC with total complexity log(N) + sqrt(N).
used precalculation of number of divisors. but got 3 tles for using cin and cout.
1. paste this line in main function first- "ios::sync_with_stdio(0);
@starters12 i also implemented the same in java getting tle
Count divisor between gcd(a,b) in sqrt.