← All solutions

First we note that the number of multiplications used in any solution must be small: there can be at most 29 of them (since if m > 1 using more multiplications inevitably gives us numbers larger than 10⁹, and if m = 1 multiplications are useless). So we’ll try all possible values g for the number of multiplication operations used by the solution.

Next, given the value of g we’ll have to figure out how to do the additions. For 0 ≤ i ≤ g, let us denote by h_i the number of additions performed between the i’th and (i + 1)’th multiplication operations. So for example h₀ is the number of additions performed before the first multiplication and h_g is the number of additions after the last one. Then, the resulting program transforms input x to α(x) = x·m^g + a·∑_i=0^g h_i·m^g−i. The constraint that the input range [p, q] is mapped to [r, s] is then equivalent with requiring that ∑_i=0^g h_i·mⁱ lies in the interval [(r − p·m^g)/a, (s − q·m^g)/a]. Let us denote this new interval by [u, v]. If [u, v] contains no integers, it will be impossible to choose valid h_i’s (for this choice of g). Otherwise, there is a solution.

To minimize the total number of operations, i.e., the sum of the h_i’s (plus g, which is fixed at this point) we can choose the h_i’s in a greedy fashion: starting from h_g working our way down to h₀, try to choose h_i to be as large as possible without having ∑_i=0^g h_i·mⁱ exceeding v, with the exception that once the sum goes beyond u we should stop.

What remains is to be able to compare solutions to pick the lexicographically smallest shortest one, we’ll leave this to the reader.