Hello everyone,
here is a very simple idea that can be useful for (cp) number theory problems, especially those concerning multiples, divisors, $$$\text{GCD}$$$ and $$$\text{LCM}$$$.
Prerequisites: basic knowledge of number theory (divisibility, $$$\text{GCD}$$$ and $$$\text{LCM}$$$ properties, prime sieve).
Idea
Let's start from a simple problem.
You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. Let $$$m$$$ be the maximum $$$a_i$$$. For each $$$k$$$, let $$$f(k)$$$ be the sum of the $$$b_i$$$ such that $$$k | a_i$$$. Output all pairs $$$(k, f(k))$$$ such that $$$f(k) > 0$$$.
An obvious preprocessing is to calculate, for each $$$k$$$, the sum of the $$$b_i$$$ such that $$$a_i = k$$$ (let's denote it as $$$g(k)$$$). Then, there are at least $$$3$$$ solutions to the problem.
Solution 1: $$$O(m\log m)$$$
For each $$$k$$$, $$$f(k) = \sum_{i=1}^{\lfloor m/k \rfloor} g(ik)$$$. The complexity is $$$O\left(m\left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m}\right)\right) = O(m\log m)$$$.
Solution 2: $$$O(n\sqrt m)$$$
There are at most $$$n$$$ nonzero values of $$$g(k)$$$. For each one of them, find the divisors of $$$k$$$ in $$$O(\sqrt k)$$$ and, for each divisor $$$i$$$, let $$$f(i) := f(i) + g(k)$$$.
If $$$m$$$ is large, you may need to use a map to store the values of $$$f(k)$$$ but, as there are $$$O(n\sqrt[3] m)$$$ nonzero values of $$$f(k)$$$, the updates have a complexity of $$$O(n\sqrt[3] m \log(nm)) < O(n\sqrt m)$$$.
Solution 3: $$$O(m + n\sqrt[3] m)$$$
Build a linear prime sieve in $$$[1, m]$$$. For each nonzero value of $$$g(k)$$$, find the prime factors of $$$k$$$ using the sieve, then generate the divisors using a recursive function that finds the Cartesian product of the prime factors. Then, calculate the values of $$$f(k)$$$ like in solution 2.
Depending on the values of $$$n$$$ and $$$m$$$, one of these solutions can be more efficient than the others.
Even if the provided problem seems very specific, the ideas required to solve that task can be generalized to solve a lot of other problems.
Hint 1$$$\text{LCM}$$$ is quite uncomfortable. Rephrase the problem using $$$\text{GCD}$$$.
Hint 2Use $$$\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$$$?
Hint 3For 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$$$?
SolutionYou 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).
Hint 1Once again, use $$$\text{GCD}$$$ instead of $$$\text{LCM}$$$ and solve the problem for each fixed $$$\text{GCD}$$$.
Hint 2Let $$$\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)?
Hint 3Let $$$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?
SolutionYou 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).
Implementation (C++)
Hint 1Suppose 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)?
Hint 2It'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?
Hint 3The 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?
Hint 4If $$$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$$$?
SolutionIt'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$$$.
Implementation (C++)
Other problems
1493D - GCD of an Array (suggested by nor)
1436F - Sum Over Subsets (nor)
Codechef — Chefsums (nor)
Conclusions
We've seen that this technique is very flexible. You can choose the complexity on the basis of the constraints, and $$$f(k)$$$ can be anything that can be updated fast.
Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems that can be solved with this technique.
I hope you enjoyed the blog!