Sieve trick — Storing information about multiples/divisors

Revision en2, by TheScrasse, 2021-06-12 11:54:42

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)$.

#### 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)