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.

Solution 1: $$$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)$$$.

Solution 2: $$$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)$$$.

Solution 3: $$$O(m + n\sqrt[3] m)$$$

Build a linear prime sieve in $$$[1, m]$$$. For each nonzero value of $$$g(i)$$$, find the prime factors of $$$i$$$ 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(i)$$$ 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 a lot of other problems.