# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

EASY

# PROBLEM:

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.

# EXPLANATION:

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.

## Proof

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.

## Naive solution

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.

## Proof

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.

# TIME COMPLEXITY:

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.

# SOLUTIONS:

Editorialist’s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters