TheScrasse's blog

[Tutorial] Number theory — Storing information about multiples/divisors
By TheScrasse, history, 4 years ago, In English

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

Prerequisites: basic knowledge of number theory (divisibility, $$$\text{GCD}$$$ and $$$\text{LCM}$$$ properties, prime sieve).

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 | a_i$$$. Output all pairs $$$(k, f(k))$$$ such that $$$f(k) > 0$$$.

An obvious preprocessing is to calculate, for each $$$k$$$, the sum of the $$$b_i$$$ such that $$$a_i = k$$$ (let's denote it as $$$g(k)$$$). Then, there are at least $$$3$$$ solutions to the problem.

Solution 1: $$$O(m\log m)$$$

For each $$$k$$$, $$$f(k) = \sum_{i=1}^{\lfloor m/k \rfloor} g(ik)$$$. The complexity is $$$O\left(m\left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m}\right)\right) = O(m\log m)$$$.

Solution 2: $$$O(n\sqrt m)$$$

There are at most $$$n$$$ nonzero values of $$$g(k)$$$. For each one of them, find the divisors of $$$k$$$ in $$$O(\sqrt k)$$$ and, for each divisor $$$i$$$, let $$$f(i) := f(i) + g(k)$$$.
If $$$m$$$ is large, you may need to use a map to store the values of $$$f(k)$$$ but, as there are $$$O(n\sqrt[3] m)$$$ nonzero values of $$$f(k)$$$, 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(k)$$$, find the prime factors of $$$k$$$ 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(k)$$$ 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
Solution

agc038_c - LCMs

Hint 1
Hint 2
Hint 3
Solution

Implementation (C++)

abc191_f - GCD or MIN

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

1493D - GCD of an Array (suggested by nor)
1436F - Sum Over Subsets (nor)
Codechef — Chefsums (nor)

Conclusions

We've seen that this technique is very flexible. You can choose the complexity on the basis of the constraints, and $$$f(k)$$$ can be anything that can be updated fast.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems that can be solved with this technique.

I hope you enjoyed the blog!

  • Vote: I like it
  • +105
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Nice blog! I like solving problems which use such ideas, so here are a few more problems with a similar flavour:

1436F - Sum Over Subsets

Chefsums

1493D - GCD of an Array

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The Solution spoiler for 1154G - Minimum Possible LCM seems to be broken, I see this:

broken

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Fixed. I don't know the reason of the failed parsing, though. The original text was

    Spoiler

    and I had to change it to

    Spoiler
    → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Solution 1 can be easily optimized to $$$O(m \log{\log{m}})$$$ using the same idea as calculating sums-over-submasks. The code looks something like this:

vector<int> f = g;
for (int p : primes)
  for (int i = m / p; i > 0; --i)
    f[i] += f[i*p];

I suspect there are very few (if any) problems in practice for which solution 3 is directly applicable, but this optimized solution 1 is not.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain k | a[i] meaning? :v

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I find a couple of good idea's in this blog. Sometimes i was stuck due to lack of number theory like in 1366D - Two Divisors i was stuck for a long time and then i recently solve it using Sieve of Eratosthenes. It's good to learn how to use G.C.D and L.C.M in number theory problems because because most of the times in cp you have to use it if you don't know how to use number theory then you will be in loss.

→ Reply