\(X,Y\) を決め打ったとき、赤い袋に入った整数全体の最大公約数が \(X\) の倍数、青い袋に入った整数全体の最大公約数が \(Y\) の倍数になるような袋への入れ方が存在するかどうかは \(O(N)\) 時間で判定可能です。そこで、\(X,Y\) を全探索することを考えましょう。

\(a_1\) を赤い袋に、\(b_1\) を青い袋に入れることを仮定します。 このとき、\(X,Y\) はそれぞれ \(a_1,b_1\) の約数となり、\(X,Y\) の候補は \(d(n)\) を \(n\) の約数の個数として \(d(a_1)d(b_1)\) 通り試せば十分です。

このアルゴリズムは時間計算量 \(O(d(a_1)d(b_1)N)\) で動作し、十分高速です。