In this blog I am going to present you a very interesting concept or a technique, I don't know exactly what it is, because I cannot remember where I learned it from.

The thing that makes it so special for me is its simplicity, because it usually doesn't require a lot of thinking or deep knowledge in number theory or mathematics as general.

As you may have guessed by the title of this article it uses dynamic programming to solve problems related to number theory. More specifically, it in my opinion is very appropriate for problems that require us to find the the number of pairs that satisfy some divisibility condition (usually gcd or something like this). Most of the problems presented in this article will probably have a solution using Möbius inversion or some combinatorial approach (usually the inclusion-exclusion principle). If you want to study more about Möbius inversion you can check this out.

The technique is really simple and is based on, roughly speaking, overcounting and compensating for it. I will start explaining with a very popular example. Find the number of coprime pairs of integers from $$$1$$$ to $$$n$$$. This, as I mentioned earlier, can be done using Möbius inversion or inclusion-exclusion principle, but I won't talk about them in this blog. However, there are some similarities between the solutions that I will present and the ones using the other techniques, so check them out if you are not familiar with them. So without anything further to do, let's begin with the solution.

Initially we will begin by getting a rough estimate for the actual values. What I mean by that, for example if two numbers have a greatest common divisor $$$d$$$, both of them should be at least divisible by $$$d$$$. So we can say that all pairs of numbers that have gcd $$$d$$$ will be contained in the set of pairs of numbers, where both of the numbers are divisible by $$$d$$$. More specifically the amount of these pairs is $$$\frac{\lfloor n/d \rfloor(\lfloor n/d \rfloor-1)}{2}$$$. But what exactly does this number contain. If we think about it, it includes all pairs of numbers that have gcd greater than or equal to $$$d$$$, more specifically the greatest common divisors can be expressed as $$$k \cdot d$$$ where $$$k \geq 1$$$. Let's store these values in an array called, for example, $$$dp$$$, where $$$dp[d] = \frac{\lfloor n/d \rfloor(\lfloor n/d \rfloor-1)}{2}$$$. From now on we will try to exclude from $$$dp[d]$$$ all the pairs that don't have exactly $$$d$$$ as gcd.

Let's analyze the array a little bit. We can see that some of the values are actually correct. For example $$$dp[n]$$$ is right, because we cannot have a pair of integers that have gcd $$$2n$$$, simply because all numbers are $$$\leq n$$$. If we try to go a little bit further we can see that for example $$$dp[n/2]$$$ is equal to $$$dp[n/2] - dp[n]$$$ (of course assuming that n is an even number). This is true because $$$dp[n/2]$$$ stores only pairs that have gcd $$$n/2$$$ or $$$n$$$, but $$$dp[n]$$$ has the exact number of pairs, so after all the number that is left in $$$dp[n/2]$$$ becomes correct as well.

So let's try to generalize this a little bit. if we have some $$$d$$$ then $$$dp[d]$$$ will contain the values for $$$d, 2d, 3d, ...$$$ and so on. This means that the only thing that we have to do is to exclude these values and leave only the correct one for $$$d$$$. We can get these values from the other values of the array $$$dp$$$, i.e. — $$$dp[2d], dp[3d], ...$$$ and if some of them are not correct we can compute them first. This will work, because the "chain" of values that we will have to compute will only increase, so it will eventually reach a point, when the value is correct, therefore we can compute all of them.

To summarize, we will outline an algorithm, which solves this particular task and which we will use later as a model for the other problems. Initially we will read $$$n$$$ and will populate the array $$$dp$$$ as we mentioned earlier. We will start iterating a variable $$$d$$$ from $$$n$$$ down to $$$1$$$ and we will do the following thing — start iterating a value $$$k$$$, which start from $$$2d$$$ and increases by $$$d$$$ at each step, until it becomes greater than $$$n$$$. For each step of $$$k$$$ we will decrease the value of $$$dp[d]$$$ by $$$dp[k]$$$ (since we are going in decreasing order of $$$d$$$, $$$dp[k]$$$ is always correct).

Example 1

Problem: You are given an array $$$a$$$. Calculate the number of pairs $$$i<j$$$, so that $$$gcd(a[i], a[j])=1.$$$ Solution: This technique can be very easily extended to this problem, since the basic one needs only the number of integers that are divisible by some number $$$d$$$. In this case we can simply factorize all numbers and get their divisors. Populate $$$dp$$$ in this way: $$$dp[d] = \frac{cntDiv[d]( cntDiv[d] - 1)}{2}$$$. So now we have exaclty the same situation as before — $$$dp[d]$$$ contains all pairs, whose $$$gcd$$$ is $$$\geq d$$$. So obviously we can run the same procedure as before on the array and the problem is solved.

Example 2

Problem: You are give an array $$$a$$$. Compute the sum of $$$lcm(a[i], a[j])$$$ for $$$i<j$$$. Solution: We will use the property that $$$lcm(x, y) = \frac{xy}{gcd(x, y)}$$$. As we have noticed this technique works great with gcds, so we will have to find a way to use this property. If for every number $$$d$$$ we can find the sum of the product of all pairs $$$(a[i], a[j])$$$ for which $$$gcd(a[i], a[j])=d$$$, we will be able to solve the problem, since we will only have to divide each of these sums by $$$d$$$ and that will be the lcms. So now the only thing that is left for us is to find the sum of $$$a[i] \cdot a[j]$$$ for each $$$d$$$ as I just mentioned. One way to do so is to calculate the sum of all numbers divisible by $$$d$$$ and the sum of the squares of all such numbers. And now the sum that we initially needed is simply $$$\frac{[SumOfNumbers]^2 - [SumOfSquaresOfNumbers]}{2}$$$. This is true because $$$[SumOfNubers] = c_1 + c_2 + c_3 + ...$$$. And when we multiply it by itself we get all pairwise products twice plus the squares of the elements, which is simply $$$[SumOfSquaresOfNumbers]$$$. After we compute the sum of all products of the pairs made of numbers divisible by $$$d$$$, we again encounter the same overcounting issue — $$$dp[d]$$$ contains pairs, whose gcd is greater than $$$d$$$. So we can exclude the redundant values again, as we did the last time and we are done.