RT，这题把 $a_1 \sim a_n$ 以及 $w$ 质因数分解之后显然有一种 $\log^2$ 量级的贪心做法。

本题复杂度瓶颈似乎在分解质因数的复杂度，不过即使这样 $w$ 至少可以开到 $10^9$。