Hints: https://atcoder.jp/contests/arc166/editorial/7374

[1] Solution (1)

We may assume that the operation for each term is one of the following.

• Do nothing.
• Increment until it is a multiple of \(a\).
• Increment until it is a multiple of \(b\).
• Increment until it is a multiple of \(c\).
• Increment until it is a multiple of \(\mathrm{lcm}(a,b)\).
• Increment until it is a multiple of \(\mathrm{lcm}(a,c)\).
• Increment until it is a multiple of \(\mathrm{lcm}(b,c)\).
• Increment until it is a multiple of \(\mathrm{lcm}(a,b,c)\).

By performing DP to decide which of the eight operations to perform on each term from front to back and calculate the minimum cost for the eight states where multiples of \(a, b, c\) exist or not at each point, you can solve the problem in \(O(N)\) time.

[2] Solution (2)

Below are the ways to achieve the goal.

• Make three different terms multiples of \(a\), \(b\), and \(c\).
• Make two different terms multiples of \(a\) and \(\mathrm{lcm}(b,c)\).
• Make two different terms multiples of \(b\) and \(\mathrm{lcm}(a,c)\).
• Make two different terms multiples of \(c\) and \(\mathrm{lcm}(a,b)\).
• Make one term a multiple of \(\mathrm{lcm}(a,b,c)\).

Let’s solve each of these cases. Since they are all the same, just the first case is explained.

Considering a naive brute-force search, it seems that you need to search \(\Theta(N^3)\) cases to decide which terms to make multiples of \(a,b,c\).

To reduce the search range, consider the properties that can be assumed in an optimal solution, and you will find, for example, the following:

• There is an optimal solution in which the term to make a multiple of \(a\) is one of the three with the smallest cost.

Indeed, you can easily prove this by considering replacing the term to make a multiple of \(a\). After narrowing down the terms to be operated on to \(O(1)\) in \(O(N)\) time and then performing a brute-force search, you can solve this case in \(O(N)\) time.