Given two positive integers a and b. You have a number x which is initially 0. At first, you can add a to x any number of times. After that, you can divide x by b any number of times.
Determine if it is possible to make x equal 1.
Say it is possible to make x equal to 1 by:
- first adding a to it n times, and then
- dividing it b, m times.
Mathematically, this can be written as
Since n is an integer, the equation implies that a divides b^m for some m. This is true if and only if b is divisible by every prime factor of a.
If there exists some p such that p|a, then
Thus, b should be divisible by every prime factor of a.
When m is large enough, the highest power of p that divides b^m will exceed the highest power of p that divides a, for all prime p, implying a|b^m.
All that remains now is to check if b is divisible by each prime factor of a.
We can calculate all prime factors of a in \sqrt a, using the Sieve of Eratosthenes. However, the time complexity over all test cases will be
which will TLE for the given constraints.
Let g = \gcd(a, b). While g \ne 1, divide a by g and repeat. If at the end, a equals 1, then b is divisible by each prime factor of a, and not otherwise.
If there exists some p such that p|a and p\nmid b, then p\nmid \gcd(a,b), a will always have a factor of p and so will never become equal to 1.
When p|b, it can be seen that the highest power of p that divides a is successively reduced to 0 on dividing by g, which implies a becomes 1 eventually.
The time complexity of this approach can be found in the corresponding section below.
Computing the gcd takes O(\log \min(a,b)). The number of prime factors in the factorisation of a is \le \log a (why?). Since in each division by g, the number of prime factors in the factorization of a is reduced (until g or a equals 1), the total time complexity is
per test case.
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)