给定 n 个数 a1,a2,…,an。
对于每一个 ai 求出它的两个不为 1 的约数 d1,d2 ,满足 gcd(d1+d2,ai)=1,或指出不存在这样的 d1,d2。
n≤5×105,2≤ai≤107
大力推一波式子:
设 gcd(d1,d2)=d,d1′=d1/d,d2′=d2/d。
那么 d1+d2=d(d1′+d2′),gcd(d1+d2,ai)=gcd(d(d1′+d2′),ai)=1。
由于 d 一定是 ai 的因子,所以 gcd(d(d1′,d2′),ai)≥d,所以 d 只能为 1。
也就是说,找到两个互质的 d1 和 d2 即可。
那么考虑线性筛预处理出每个数的最小质因子,把 ai 的最小质因子 p 除光,剩下的数 x 显然和 p 互质,特判掉 x=1 的情况即可。