\(\{ a_i \}\) の最大公約数を \(g\) として, \(\{ b_i = a_i/g \}\) とすると, \(\sum a_i = g\sum b_i\) となるので, \(g\) は \(M\) の約数でなければならない.

逆に言えば, \(M\) の約数 \(f\) について \(M/f \geq N\) であれば, \(\{ b_i \}\) を構成できるので, これを満たす最大の約数を見つけ出せばいい.

約数は \(\sqrt{M}\) の範囲までの試し割りで見つける. その見つけた約数を \(f\) とすると, \(M/f\) も約数となる.