Sieve trick — Storing information about multiples/divisors

Revision en1, by TheScrasse, 2021-06-12 11:34:23

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 $$$k$$$, let $$$f(k)$$$ be the sum of the $$$b_i$$$ such that $$$k \mid a_i$$$. Output all pairs $$$(k, f(k))$$$ such that $$$f(k) > 0$$$.

Tags number theory, gcd, lcm

History

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