Prime Reduction#13085

Prime Reduction (Editorial)

Tutorial

Let $v_{p} (x)$ v_p(x) denote the exponent of the prime $p$ in the prime factorization of $x$ .

For example, since $12 = 2^{2} \cdot 3$ 12 = 2^2 \cdot 3, we have $v_{2} (12) = 2$ v_2(12)=2 and $v_{3} (12) = 1$ v_3(12)=1.

We will first solve the problem for one fixed prime $p$ , and then combine the answers for all primes.

Observation 1: Solving the problem for one prime

Fix a prime $p$ and define

e_{i} = v_{p} (a_{i}) .

e_i = v_p(a_i).

Also define $e_{0} = 0$ e_0=0.

Consider only operations in which the chosen prime is $p$ .

If we divide some $a_{i}$ a_i by $p$ , then $e_{i}$ e_i decreases by exactly $1$ .

Therefore, an operation with prime $p$ selects a contiguous subsegment whose exponents are all positive and decreases every exponent in this subsegment by $1$ .

So, for a fixed prime $p$ , the problem becomes the following:

We have a non-negative array $e_{1}, e_{2}, \dots, e_{n}$ e_1,e_2,\ldots,e_n. In one operation, we may choose a contiguous subsegment consisting only of positive values and subtract $1$ from every value in it. We want to make the whole array equal to zero.

The minimum number of operations is

i = 1 \sum n max (0, e_{i} - e_{i - 1}) .

\sum_{i=1}^{n} \max(0,e_i-e_{i-1}).

Let us prove this formula.

Consider some level $h \geq 1$ h \ge 1.

Look at all indices for which

e_{i} \geq h .

e_i \ge h.

These indices form several maximal contiguous segments.

Each such segment needs exactly one operation at level $h$ .

A new segment at level $h$ starts at position $i$ exactly when

e_{i - 1} < h \leq e_{i} .

e_{i-1} < h \le e_i.

For a fixed position $i$ , the number of values of $h$ satisfying this inequality is exactly

max (0, e_{i} - e_{i - 1}) .

\max(0,e_i-e_{i-1}).

Therefore, after summing over all positions, the minimum number of operations using the prime $p$ is

i = 1 \sum n max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) .

\sum_{i=1}^{n} \max \left( 0, v_p(a_i)-v_p(a_{i-1}) \right).

Observation 2: Combining all primes

Now consider the contribution between positions $i - 1$ i-1 and $i$ .

For one prime $p$ , this contribution is

max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) .

\max \left( 0, v_p(a_i)-v_p(a_{i-1}) \right).

For any non-negative integers $A$ and $B$ ,

max (0, A - B) = A - min (A, B) .

\max(0,A-B)=A-\min(A,B).

Therefore,

max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) = v_{p} (a_{i}) - min (v_{p} (a_{i}), v_{p} (a_{i - 1})) .

\max \left( 0, v_p(a_i)-v_p(a_{i-1}) \right) = v_p(a_i) - \min \left( v_p(a_i),v_p(a_{i-1}) \right).

Now sum this expression over all primes $p$ .

Let $Ω (x)$ denote the total number of prime factors of $x$ , counting multiplicity.

For example,

12 = 2^{2} \cdot 3,

12=2^2\cdot3,

so

Ω (12) = 3.

\Omega(12)=3.

By definition,

p \sum v_{p} (x) = Ω (x) .

\sum_p v_p(x)=\Omega(x).

Also, for every prime $p$ ,

v_{p} (g cd (x, y)) = min (v_{p} (x), v_{p} (y)) .

v_p(\gcd(x,y)) = \min(v_p(x),v_p(y)).

Thus,

p \sum min (v_{p} (a_{i}), v_{p} (a_{i - 1})) = Ω (g cd (a_{i}, a_{i - 1})) .

\sum_p \min \left( v_p(a_i),v_p(a_{i-1}) \right) = \Omega \left( \gcd(a_i,a_{i-1}) \right).

Hence the contribution of position $i$ is

C_{i} = Ω (a_{i}) - Ω (g cd (a_{i - 1}, a_{i})) .

C_i = \Omega(a_i) - \Omega \left( \gcd(a_{i-1},a_i) \right).

We define $a_{0} = 1$ a_0=1.

Therefore, the answer for the whole array is

ans = i = 1 \sum n (Ω (a_{i}) - Ω (g cd (a_{i - 1}, a_{i}))) .

\mathrm{ans} = \sum_{i=1}^{n} \left( \Omega(a_i) - \Omega \left( \gcd(a_{i-1},a_i) \right) \right).

Notice that operations corresponding to different primes are independent: an operation using prime $p$ changes only the exponent of $p$ and does not change the exponent of any other prime.

Therefore, summing the minimum cost for every prime gives the minimum total number of operations.

Observation 3: Handling an update

Define

C (x, y) = Ω (y) - Ω (g cd (x, y)) .

C(x,y) = \Omega(y)-\Omega(\gcd(x,y)).

Then

ans = i = 1 \sum n C (a_{i - 1}, a_{i}) .

\mathrm{ans} = \sum_{i=1}^{n} C(a_{i-1},a_i).

Suppose we update position $i d x$ .

Only two contributions can contain $a_{i d x}$ a_{idx}:

C (a_{i d x - 1}, a_{i d x})

C(a_{idx-1},a_{idx})

and, if $i d x < n$ idx<n,

C (a_{i d x}, a_{i d x + 1}) .

C(a_{idx},a_{idx+1}).

Therefore, before changing $a_{i d x}$ a_{idx}, we subtract these contributions from the answer.

Then we set

a_{i d x} = x

a_{idx}=x

and add the new values of the same contributions.

So each update requires only a constant number of GCD computations.

Precomputation

All values are at most $1 0^{7}$ 10^7.

Let

M = 1 0^{7} .

M=10^7.

We precompute the smallest prime factor of every number from $1$ to $M$ using a linear sieve.

At the same time, we can compute $Ω$ .

We have

Ω (1) = 0.

\Omega(1)=0.

For every $x > 1$ x>1, if $spf (x)$ is its smallest prime factor, then

Ω (x) = Ω (\frac{x}{spf ( x )}) + 1.

\Omega(x) = \Omega \left( \frac{x}{\operatorname{spf}(x)} \right) +1.

Thus, after the precomputation, $Ω (x)$ can be obtained in constant time.

Complexity

The sieve takes

O (M)

time and

O (M)

memory.

Computing the initial answer requires $n$ GCD computations.

Each query requires only a constant number of GCD computations, and each GCD takes

O (lo g M)

\mathcal{O}(\log M)

time.

Therefore, the total time complexity is

O (M + (n + q) lo g M),

\mathcal{O} \left( M+(n+q)\log M \right),

where $M = 1 0^{7}$ M=10^7.

The memory complexity is

O (M + n) .

\mathcal{O}(M+n).

v_{p} (x)

12 = 2^{2} \cdot 3

v_{2} (12) = 2

v_{3} (12) = 1

e_{i} = v_{p} (a_{i}) .

e_{0} = 0

a_{i}

e_{i}

e_{1}, e_{2}, \dots, e_{n}

i = 1 \sum n max (0, e_{i} - e_{i - 1}) .

h \geq 1

e_{i} \geq h .

e_{i - 1} < h \leq e_{i} .

max (0, e_{i} - e_{i - 1}) .

i = 1 \sum n max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) .

i - 1

max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) .

max (0, A - B) = A - min (A, B) .

max (0, v_{p} (a_{i}) - v_{p} (a_{i - 1})) = v_{p} (a_{i}) - min (v_{p} (a_{i}), v_{p} (a_{i - 1})) .

12 = 2^{2} \cdot 3,

Ω (12) = 3.

p \sum v_{p} (x) = Ω (x) .

v_{p} (g cd (x, y)) = min (v_{p} (x), v_{p} (y)) .

p \sum min (v_{p} (a_{i}), v_{p} (a_{i - 1})) = Ω (g cd (a_{i}, a_{i - 1})) .

C_{i} = Ω (a_{i}) - Ω (g cd (a_{i - 1}, a_{i})) .

a_{0} = 1

ans = i = 1 \sum n (Ω (a_{i}) - Ω (g cd (a_{i - 1}, a_{i}))) .

C (x, y) = Ω (y) - Ω (g cd (x, y)) .

ans = i = 1 \sum n C (a_{i - 1}, a_{i}) .

a_{i d x}

C (a_{i d x - 1}, a_{i d x})

i d x < n

C (a_{i d x}, a_{i d x + 1}) .

a_{i d x}

a_{i d x} = x

1 0^{7}

M = 1 0^{7} .

Ω (1) = 0.

x > 1

Ω (x) = Ω (\frac{x}{spf ( x )}) + 1.

O (lo g M)

O (M + (n + q) lo g M),

M = 1 0^{7}

O (M + n) .