rt,本题在思路上与 https://www.luogu.com.cn/problem/CF1225D 相似，只是把 $a_{i}$ 的范围放大，但也是在可以质因数分解的范围