First, we can divide the problem into sub-problems for each multiset of prime factors other than \(2\) and \(3\). That is, for each non-negative integer \(u \leq N\) that is neither a multiple of \(2\) nor \(3\), consider the following problem:

Let \(T(u)\) be the set of integers not greater than \(\displaystyle \frac{N}{u}\) that can be expressed as \(2^a 3^b\) using non-negative integers \(a\) and \(b\). Find the minimum number of operations required so that \(T(u) \subseteq S\) is satisfied through the problem’s operations.

By summing up the answers to this problem for all \(u\), we obtain the answer to the original problem. Let’s focus on this problem first.

Consider the \(ab\) plane, and associate the integer \(2^a 3^b\) with the lattice point \((a, b)\) on this plane. In this context, the operation of the problem can be interpreted as selecting a lattice point \((x, y) \ (x, y \geq 0)\) and adding the integers corresponding to the lattice points \((x, y), (x + 1, y), (x, y + 1)\) to \(S\).

We consider a bit DP defined as follows:

• \(\mathrm{dp}[i][s] :=\) The minimum number of operations required to reach a state where all integers corresponding to lattice points with \(a < i\) have been added to \(S\), and among the lattice points with \(a = i\), the set of integers already in \(S\) corresponds to \(s\).

By using the fast zeta transform and appropriately transitioning, this DP can be executed in a computation time of \(\displaystyle O\left(\left(\frac{N}{u}\right)^{0.64} \log^2 \frac{N}{u}\right)\).

Returning to the original problem, it is not necessary to execute this DP for all \(u\). The number of different choices of \(u\) such that \(T(u)\) are distinct is at most roughly \((1 + \log_2 N)(1 + \log_3 N)\). Also, when \(u\) is large, the DP finishes quickly.

The intended solution (C++) has an execution time of about 700 ms. Sample Implementation

In slower languages, if you can write a DP that runs fast enough locally, you can get accepted by embedding.