Sieve trick — Storing information about multiples/divisors

Revision en4, by TheScrasse, 2021-06-12 12:12:06

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 solve a lot of other problems.

1154G - Minimum Possible LCM

Hint 1
Hint 2
Hint 3

History

Revisions

Rev. Lang. By When Δ Comment
en15 TheScrasse 2021-07-21 19:26:40 1 Tiny change: ' a_j) = h$.\n\nSo, f' -> ' a_j) = h$ .\n\nSo, f'
en14 TheScrasse 2021-06-12 22:58:38 5 Tiny change: 'that, if ${GCD}(a_i,' -> 'that, if$\text{GCD}(a_i,'
en13 TheScrasse 2021-06-12 19:09:57 15 Tiny change: 'mber of $k$ such tha' -> 'mber of $k \leq \min(a_i)$ such tha'
en12 TheScrasse 2021-06-12 14:58:51 239 Tiny change: 'em:1436F] ([user:nor' -> 'em:1436F] \([user:nor'
en11 TheScrasse 2021-06-12 14:44:35 11
en10 TheScrasse 2021-06-12 13:59:12 83
en9 TheScrasse 2021-06-12 13:58:30 23 (published)
en8 TheScrasse 2021-06-12 13:56:43 1977 Tiny change: '585)\n\n[agc191_f \- ' -> '585)\n\n[abc191_f \- '
en7 TheScrasse 2021-06-12 13:27:01 3240 Tiny change: '[agc038_c - LCMs](ht' -> '[agc038_c \- LCMs](ht'
en6 TheScrasse 2021-06-12 12:29:20 19
en5 TheScrasse 2021-06-12 12:28:13 692
en4 TheScrasse 2021-06-12 12:12:06 617 Tiny change: ' problems.' -> ' problems.\n\n[problem:1154G]\n------------------'
en3 TheScrasse 2021-06-12 12:03:04 628
en2 TheScrasse 2021-06-12 11:54:42 830 Tiny change: '\lfloor m/k \rfloor} ' -> '\lfloor m/i \rfloor} '
en1 TheScrasse 2021-06-12 11:34:23 503 Initial revision (saved to drafts)