题解

思路

交换红、蓝两袋不会改变得分，所以可以假设第一包中 $a_1$ 进入红袋、$b_1$ 进入蓝袋。

做法

于是最终红袋 gcd 的任意因数必为 $a_1$ 的因数，蓝袋同理。枚举 $a_1$ 的因数 $x$ 与 $b_1$ 的因数 $y$；对于每个卡包，只要 $(a_i\bmod x=0\land b_i\bmod y=0)$ 或 $(b_i\bmod x=0\land a_i\bmod y=0)$，就能为该包选择一种合法方向，因而这一因数对可行。

对所有可行因数对取 $\operatorname{lcm}(x,y)$ 的最大值。任意真实最优分配的两个 gcd 都会作为某个枚举对出现，所以答案不会被低估；反之，一个可行因数对可以扩展为某个分配，该分配的两个 gcd 分别是 $x,y$ 的倍数，其得分不会小于当前候选，因此取最大值恰好得到最优答案。

复杂度

用平方根枚举两个数的因数，复杂度为 $O(\sqrt{a_1}+\sqrt{b_1}+d(a_1)d(b_1)N)$，空间复杂度为 $O(d(a_1)+d(b_1))$。