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.