$$$\text{LCM}$$$ is quite uncomfortable. Rephrase the problem using $$$\text{GCD}$$$.

Use $$$\text{LCM}(a, b) = \frac{ab}{\text{GCD}(a, b)}$$$. Now you can solve the problem separately for each $$$k = \text{GCD}(a_i, a_j)$$$ ($$$i \neq j$$$). What are the optimal values of $$$a_i, a_j$$$?

For a fixed $$$k$$$, it's optimal to choose the minimum $$$a_i, a_j$$$ that are multiples of $$$k$$$. How to find those minimums? Does it matter if, actually, $$$\text{GCD}(a_i, a_j) > k$$$?

You have to minimize $$$\frac{a_ia_j}{\text{GCD}(a_i, a_j)}$$$ ($$$i \neq j$$$).

For each $$$k = \text{GCD}(a_i, a_j)$$$, $$$a_i, a_j$$$ have to be multiples of $$$k$$$. Note that, if $$$\text{GCD}(a_i, a_j) = h > k$$$, you end up calculating a wrong value of $$$\text{LCM}(a_i, a_j)$$$, but it doesn't matter because it's never optimal; you will calculate the correct (smaller) value of the $$$\text{LCM}$$$ while considering $$$\text{GCD}(a_i, a_j) = h$$$ .

So, for each $$$k$$$, it's enough to consider the smallest $$$a_i, a_j$$$ that are multiples of $$$k$$$. You can find them like in Solution 1 or Solution 3 (instead of the sum, you should keep the two minimum elements).

Once again, use $$$\text{GCD}$$$ instead of $$$\text{LCM}$$$ and solve the problem for each fixed $$$\text{GCD}$$$.

Let $$$\displaystyle g(k) = \sum_{k | a_i, k | a_j, i < j}a_ia_j$$$. Can you calculate it with Solution 1 (or Solution 3)?

Let $$$g_1(k) = \sum_{k | a_i}a_i$$$, $$$g_2(k) = \sum_{k | a_i}a_i^2$$$ (they can be calculated with Solution 1 or Solution 3). Then, $$$g(k) = \frac{1}{2}(g_1(k)^2 - g_2(k))$$$ (it's easy to prove).

Now the problem is that some products $$$a_ia_j$$$ considered in $$$g(k)$$$ may have $$$\text{GCD}(a_i, a_j) > k$$$. How to fix that?

You have to calculate the sum of $$$\frac{a_ia_j}{\text{GCD}(a_i, a_j)}$$$ ($$$i < j$$$).

For each $$$k = \text{GCD}(a_i, a_j)$$$, $$$a_i, a_j$$$ have to be multiples of $$$k$$$. Let's start by calculating $$$\displaystyle g(k) = \sum_{k | a_i, k | a_j, i < j}a_ia_j$$$, then we will remove pairs such that $$$\text{GCD}(a_i, a_j) > k$$$.

Let $$$g_1(k) = \sum_{k | a_i}a_i$$$, $$$g_2(k) = \sum_{k | a_i}a_i^2$$$ (they can be calculated with Solution 1 or Solution 3, using $$$b_i = a_i$$$ and $$$b_i = a_i^2$$$ respectively). Note that $$$\displaystyle g_2(k) = \sum_{k | a_i, k | a_j}a_ia_j$$$. Then, $$$g(k) = \frac{1}{2}(g_1(k)^2 - g_2(k))$$$.

Finally, let $$$\displaystyle f(k) = \sum_{\text{GCD}(a_i, a_j) = k, i < j}a_ia_j$$$. Let's calculate $$$f(k)$$$ for $$$k$$$ from $$$m$$$ to $$$1$$$. Then, $$$f(k) = g(k) - \sum_{i=2}^{\lfloor m/k \rfloor} f(ik)$$$ (it's the same idea as the Solution 1).

Suppose you want the last number of the blackboard to be $$$k$$$. Is there an optimal order of operations (such that, if $$$k$$$ can be reached, you can also reach it with that order of operations)?

It's optimal to use all the $$$\text{GCD}$$$ operations before all the $$$\text{MIN}$$$ operations. So, how does the last number of the blackboard look like?

The last number of the blackboard is $$$\leq \min(a_i)$$$, and it's the $$$\text{GCD}$$$ of a subset of $$$a$$$. How to count the possible final numbers?

If $$$k$$$ is the $$$\text{GCD}$$$ of some subset, it's also the $$$\text{GCD}$$$ of $$$S_k = \{a_i \mid k | a_i\}$$$. How to calculate the $$$\text{GCD}$$$ of $$$S_k$$$ for each $$$k$$$?

It's easy to prove that the final number on the blackboard is $$$\leq \min(a_i)$$$, and it's the $$$\text{GCD}$$$ of a subset of $$$a$$$.

For a fixed $$$k$$$, a necessary and sufficient condition for it to be the $$$\text{GCD}$$$ of a subset is to be the $$$\text{GCD}$$$ of the "worst-case" subset, namely $$$S_k = \{a_i \mid k | a_i\}$$$. Let $$$f(k)$$$ be such $$$\text{GCD}$$$.

Initially, all $$$f(k)$$$ are set to $$$0$$$. For each $$$a_i$$$, iterate over its divisors $$$j$$$ (with Solution 2) and set $$$f(j) := \text{GCD}(f(j), a_i)$$$

The answer is the number of $$$k \leq \min(a_i)$$$ such that $$$f(k) = k$$$.

Suppose that you can use $$$x$$$ operations of type $$$1$$$ and $$$y$$$ operations of type $$$2$$$. Try to reorder the operations in such a way that $$$a$$$ becomes the minimum possible.

You should use operations of type $$$2$$$ first, then moves of type $$$1$$$. How many operations do you need in the worst case? ($$$a = 10^9$$$, $$$b = 1$$$)

You need at most $$$30$$$ operations. Iterate over the number of operations of type $$$2$$$.

Notice how it is never better to increase $$$b$$$ after dividing ($$$\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$$$).

So we can try to increase $$$b$$$ to a certain value and then divide $$$a$$$ by $$$b$$$ until it is $$$0$$$. Being careful as not to do this with $$$b<2$$$, the number of times we divide is going to be $$$O(\log a)$$$. In particular, if you reach $$$b \geq 2$$$ (this requires at most $$$1$$$ move), you need at most $$$\lfloor \log_2(10^9) \rfloor = 29$$$ moves to finish.

Let $$$y$$$ be the number of moves of type $$$2$$$; we can try all values of $$$y$$$ ($$$0 \leq y \leq 30$$$) and, for each $$$y$$$, check how many moves of type $$$1$$$ are necessary.

Complexity: $$$O(\log^2 a)$$$.

If we notice that it is never convenient to increase $$$b$$$ over $$$6$$$, we can also achieve a solution with better complexity.

You can make a $$$k$$$-similar array by assigning $$$a_i = x$$$ for some $$$l \leq i \leq r$$$ and $$$1 \leq x \leq k$$$.

How many $$$k$$$-similar arrays can you make if $$$x$$$ is already equal to some $$$a_i$$$ ($$$l \leq i \leq r$$$)?

How many $$$k$$$-similar arrays can you make if either $$$x < a_l$$$ or $$$x > a_r$$$?

How many $$$k$$$-similar arrays can you make if none of the previous conditions holds?

Let's consider each value $$$x$$$ from $$$1$$$ to $$$k$$$.

• If $$$x < a_l$$$, you can replace $$$a_l$$$ with $$$x$$$ (and you get $$$1$$$ $$$k$$$-similar array). There are $$$a_l-1$$$ such values of $$$x$$$.
• If $$$x > a_r$$$, you can replace $$$a_r$$$ with $$$x$$$ (and you get $$$1$$$ $$$k$$$-similar array). There are $$$k-a_r$$$ such values of $$$x$$$.
• If $$$a_l < x < a_r$$$, and $$$x \neq a_i$$$ for all $$$i$$$ in $$$[l, r]$$$, you can either replace the rightmost $$$b_i$$$ which is less than $$$x$$$, or the leftmost $$$b_i$$$ which is greater than $$$x$$$ (and you get $$$2$$$ $$$k$$$-similar arrays). There are $$$(a_r - a_l + 1) - (r - l + 1)$$$ such values of $$$x$$$.
• If $$$x = a_i$$$ for some $$$i$$$ in $$$[l, r]$$$, no $$$k$$$-similar arrays can be made.

The total count is $$$(a_l-1)+(k-a_r)+2((a_r - a_l + 1) - (r - l + 1))$$$, which simplifies to $$$k + (a_r - a_l + 1) - 2(r - l + 1)$$$.

Complexity: $$$O(n + q)$$$.

Let $$$\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$$$. Is there an upper bound for $$$k$$$?

$$$k \leq \sqrt x$$$. For a fixed $$$k$$$, can you count the number of special pairs such that $$$a \leq x$$$ and $$$b \leq y$$$ in $$$O(1)$$$?

We can notice that, if $$$\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$$$, then $$$a$$$ can be written as $$$kb+k$$$ ($$$b > k$$$). Since $$$b > k$$$, we have that $$$k^2 < kb+k = a \leq x$$$. Hence $$$k \leq \sqrt x$$$.

Now let's count special pairs for any fixed $$$k$$$ ($$$1 \leq k \leq \sqrt x$$$). For each $$$k$$$, you have to count the number of $$$b$$$ such that $$$b > k$$$, $$$1 \leq b \leq y$$$, $$$1 \leq kb+k \leq x$$$. The second condition is equivalent to $$$1 \leq b \leq x/k-1$$$.

Therefore, for any fixed $$$k > 0$$$, the number of special pairs ($$$a\leq x$$$; $$$b \leq y$$$) is $$$max(0, min(y,x/k-1) - k)$$$. The result is the sum of the number of special pairs for each $$$k$$$.

Complexity: $$$O(\sqrt x)$$$.

Brute force doesn't work (even if you optimize it): there are relatively few solutions.

There may be very few possible values of $$$b_{i,j}$$$, if $$$b_{i-1,j}$$$ is fixed. The problem arises when you have to find a value for a cell with, e.g., $$$4$$$ fixed neighbors. Try to find a possible property of the neighbors of $$$(i, j)$$$, such that at least a solution for $$$b_{i,j}$$$ exists.

The least common multiple of all integers from $$$1$$$ to $$$16$$$ is less than $$$10^6$$$.

Build a matrix with a checkerboard pattern: let $$$b_{i, j} = 720720$$$ if $$$i + j$$$ is even, and $$$720720+a_{i, j}^4$$$ otherwise. The difference between two adjacent cells is obviously a fourth power of an integer. We choose $$$720720$$$ because it is $$$\operatorname{lcm}(1, 2, \dots, 16)$$$. This ensures that $$$b_{i, j}$$$ is a multiple of $$$a_{i, j}$$$, because it is either $$$720720$$$ itself or the sum of two multiples of $$$a_{i, j}$$$.

Complexity: $$$O(nm)$$$.

What happens if you can't swap coins?

Let $$$dp_i$$$ be the maximum score that you can reach after $$$dist(1, i)$$$ moves if there is a red coin on node $$$i$$$ after step $$$3$$$. However, after step $$$2$$$, the coin on node $$$i$$$ may be either red or blue. Try to find transitions for both cases.

If you consider only the first case, you solve the problem if there are no swaps. You can greedily check the optimal location for the blue coin: a node $$$j$$$ such that $$$dist(1,i) = dist(1,j)$$$ and $$$a_j$$$ is either minimum or maximum.

Instead, if the coin on node $$$i$$$ is blue after step $$$2$$$, the red coin is on node $$$j$$$ and you have to calculate $$$\max(dp_{parent_j} + |a_j - a_i|)$$$ for each $$$i$$$ with a fixed $$$dist(1, i)$$$. How?

Divide the nodes in groups based on the distance from the root. Then, for each $$$dist(1, i)$$$ in increasing order, calculate $$$dp_i$$$ — the maximum score that you can reach after $$$dist(1, i)$$$ moves if there is a red coin on node $$$i$$$ after step $$$3$$$. You can calculate $$$dp_i$$$ if you know $$$dp_j$$$ for each $$$j$$$ that belongs to the previous group. There are two cases:

• if after step $$$2$$$ the coin on node $$$i$$$ is red, the previous position of the red coin is fixed, and the blue coin should reach either the minimum or the maximum $$$a_j$$$ among the $$$j$$$ that belong to the same group of $$$i$$$;

• if after step $$$2$$$ the coin on node $$$i$$$ is blue, there is a red coin on node $$$j$$$ ($$$dist(1, i) = dist(1, j)$$$), so you have to maximize the score $$$dp_{parent_j} + |a_j - a_i|$$$.
  This can be done efficiently by sorting the $$$a_i$$$ in the current group and calculating the answer separately for $$$a_j \leq a_i$$$ and $$$a_j > a_i$$$; for each $$$i$$$ in the group, the optimal node $$$j$$$ either doesn't change or it's the previous node.
  Alternatively, you can notice that $$$dp_{parent_j} + |a_j - a_i| = \max(dp_{parent_j} + a_j - a_i, dp_{parent_j} + a_i - a_j)$$$, and you can maximize both $$$dp_{parent_j} + a_j - a_i$$$ and $$$dp_{parent_j} + a_i - a_j$$$ greedily (by choosing the maximum $$$dp_{parent_j} + a_j$$$ and $$$dp_{parent_j} - a_j$$$, respectively). In this solution, you don't need to sort the $$$a_i$$$.

The answer is $$$\max(dp_i)$$$.

Complexity: $$$O(n)$$$ or $$$O(n\log n)$$$.

Why isn't the answer $$$2^{n-1}$$$? What would you overcount?

Find a dp with time complexity $$$O(n^2\log n)$$$.

Let $$$dp_{i, j}$$$ be the number of hybrid prefixes of length $$$i$$$ and sum $$$j$$$. The transitions are $$$dp_{i, j} \rightarrow dp_{i+1, j+b_i}$$$ and $$$dp_{i,j} \rightarrow dp_{i+1,b_i}$$$. Can you optimize it to $$$O(n\log n)$$$?

For each $$$i$$$, you can choose either $$$a_i = b_i$$$ or $$$a_i = b_i - \sum_{k=1}^{i-1} a_k$$$. If $$$\sum_{k=1}^{i-1} a_k = 0$$$, the two options coincide and you have to avoid overcounting them.

This leads to an $$$O(n^2\log n)$$$ solution: let $$$dp_i$$$ be a map such that $$$dp_{i, j}$$$ corresponds to the number of ways to create a hybrid prefix $$$[1, i]$$$ with sum $$$j$$$. The transitions are $$$dp_{i, j} \rightarrow dp_{i+1, j+b_i}$$$ (if you choose $$$b_i = a_i$$$, and $$$j \neq 0$$$), $$$dp_{i,j} \rightarrow dp_{i+1,b_i}$$$ (if you choose $$$b_i = \sum_{k=1}^{i} a_k$$$).

Let's try to get rid of the first layer of the dp. It turns out that the operations required are

• move all $$$dp_j$$$ to $$$dp_{j+b_i}$$$
• calculate the sum of all $$$dp_j$$$ in some moment
• change the value of a $$$dp_j$$$

and they can be handled in $$$O(n\log n)$$$ with "Venice technique".

$$$dp$$$ is now a map such that $$$dp_j$$$ corresponds to the number of ways to create a hybrid prefix $$$[1, i]$$$ such that $$$\sum_{k=1}^{i} a_k - b_k = j$$$. Calculate the dp for all prefixes from left to right. if $$$b_i = a_i$$$, you don't need to change any value of the dp; if $$$b_i = \sum_{k=1}^{i} a_k$$$, you have to set $$$dp_{\sum_{k=1}^{i} -b_k}$$$ to the total number of hybrid arrays of length $$$i-1$$$.

Complexity: $$$O(n\log n)$$$.

Solve some small tests on paper.

Suppose that the answer is NO. Which property should hold for the array $$$a$$$?

Solve on paper

3 3
1 1 1
1 1 1
1 1 1

3 3
2 1 1
1 1 2
2 1 2

How does the xor of all the array change after every operation?