Sieve trick — Storing information about multiples/divisors

Revision en3, by TheScrasse, 2021-06-12 12:03:04

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


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.

Tags number theory, gcd, lcm


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