正整数 \(n\)、素数 \(p\) に対し、\(n\) が \(p^k\) の倍数となるような最大の整数 \(k\) を \(v_p(n)\) とします。

最小の最適解 \(x\) の構造について整理します。

\(x\) は \(D\) の倍数でないため、ある素数 \(p\) が存在し、\(v_p(x) < v_p(D)\) となります。

このような素数を固定したとき、\(p\) と異なる素数 \(q, r\) について、\(q < r \implies v_q(x) \geq v_r(x)\) となります。これは、\(a \coloneqq v_q(x)\)、\(b \coloneqq v_r(x)\) として \(a < b\) のとき \(x\) と \(\displaystyle x\left(\frac{q}{r}\right)^{b-a}\) の約数の個数は等しく、\(x > \displaystyle x\left(\frac{q}{r}\right)^{b-a}\) であるため \(x\) の最小性から従います。また、同様に \(q < p\) なる素数 \(q\) について \(v_q(x) \geq v_p(x)\) も従います。

上の条件を満たす \(10^{18}\) 以下の整数 \(x\) は実際に列挙すると \(281944\) 個しかなく、全探索が十分高速です。実装の際は、総積が \(10^{18}\) 以下となるように、高々 \(1\) 要素を除いて広義単調減少であり、除いた \(1\) 要素も（存在すれば）直前の要素以下の値になっているような指数部分に対応する正整数列（に対応する整数）を列挙すればよいです。このように探索を行うことで、列挙する各整数の約数の個数も同時に計算することができます。

なお、\(q < p\) なる素数 \(q\) に対して \(v_q(x) \geq v_p(x)\) となる条件を用いなかったり、\(p\) を決め打って複数の \(p\) から同じ整数を探索してしまうような方針でも十分探索する個数は少なく、これらに似た多くの方針は適切な実装のもと十分高速です。