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}$$$.
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 $$$i$$$, let $$$f(i)$$$ be the sum of the $$$b_j$$$ such that $$$i \mid a_j$$$. Output all pairs $$$(i, f(i))$$$ such that $$$f(i) > 0$$$.
An obvious preprocessing is to calculate, for each $$$i$$$, the sum of the $$$b_j$$$ such that $$$a_j = i$$$ (let's denote it as $$$g(i)$$$). Then, there are at least $$$3$$$ solutions to the problem.
$$$O(m\log m)$$$
For each $$$i$$$, $$$f(i) = \sum_{j=1}^{\lfloor m/i \rfloor} g(ij)$$$. The complexity is $$$O(m(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m})) = O(m\log m)$$$.
$$$O(n\sqrt m)$$$
There are at most $$$n$$$ nonzero values of $$$g(i)$$$. For each one of them, find the divisors of $$$i$$$ in $$$O(\sqrt i)$$$ and, for each divisor $$$j$$$, let $$$f(j) := f(j) + g(i)$$$.
If $$$m$$$ is large, you may need to use a map to store the values of $$$f(i)$$$ but, as there are $$$O(n\sqrt[3] m)$$$ nonzero values of $$$f(j)$$$, the updates have a complexity of $$$O(n\sqrt[3] m \log(nm)) < O(n\sqrt m)$$$.
