### 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)