PROBLEM LINK:
Author: Vitalij Kozhukhivskij
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Easy
PREREQUISITES:
Basic maths, greatest common divisor (gcd)
PROBLEM:
Given two numbers, determine if the first number is divisible by all prime divisors of the second number.
EXPLANATION:
We are given two integers A and B, and we want to determine whether there exist a prime number which divides B, but not A.
If B = 1, then clearly there is no such prime, as B has no prime divisors.
Now assume that B > 1. Let us say d = \gcd (A, B). If any prime number divides both A and B, then it must also divide d. In other words, d contains all common prime divisors of A and B.
If d = 1, that means, there is no common prime divisor between A and B. In this case, clearly, B has a prime divisor which does not divide A, in fact all prime divisors of B fall in this category.
On the other hand, if d > 1, then B = d * (B / d). Since d contains only those primes which divide A as well, hence, B will have a prime divisor not dividing A, if and only if (B/d) has such a prime divisor. So now we have reduced the task for pair (A, B) to the pair (A, B/d). Using this we can implement an easy recursive approach as shown below.
bool HasUniquePrime(int A, int B) {
if (B == 1) return false;
int d = gcd(A, B);
if (d == 1) return true;
return HasUniquePrime(A, B/d);
}
Since each step reduces B by a factor greater than one, the recursion will terminate at most after (\log B) steps. Also, in each step we are calculating gcd, which takes O (\log \min (A, B)) time. Hence, the overall complexity of this approach is O (\log^2 B)
Time Complexity:
O (\log^2 B)
) and as such that task proved to be quite difficultā¦ I was familiar with the simple sieving methods for finding prime numbers (Erathostenes, Atkin sieves) and was familiar (not implementation-wise, I canāt implement almost any algorithm without having to look it up or see my own old codes from uni) with randomized primality testing methods like Pollard-Rho thanks to previous codechef contests, so, after a very long while, my idea was to extend these methods to factorize large integers but even Pollard-Rho was proving insufficient for thisā¦ Even with small pre-calculated prime tables it was always really slow for these contraints.