CF1366D Two Divisors 做题记录

给定 nn 个数 a1,a2,,ana_1,a_2,\dots ,a_n

对于每一个 aia_i 求出它的两个不为 11 的约数 d1,d2d_1,d_2 ,满足 gcd(d1+d2,ai)=1\gcd(d_1 + d_2, a_i) = 1,或指出不存在这样的 d1,d2d_1,d_2

n5×105n\leq 5\times 10^52ai1072\le a_i\le 10^7

大力推一波式子:

gcd(d1,d2)=d\gcd(d_1,d_2)=dd1=d1/d,d2=d2/dd_1'=d_1/d,d_2'=d_2/d

那么 d1+d2=d(d1+d2)d_1+d_2=d(d_1'+d_2')gcd(d1+d2,ai)=gcd(d(d1+d2),ai)=1\gcd(d_1+d_2,a_i)=\gcd(d(d_1'+d_2'),a_i)=1

由于 dd 一定是 aia_i 的因子,所以 gcd(d(d1,d2),ai)d\gcd(d(d_1',d_2'),a_i)\ge d,所以 dd 只能为 11

也就是说,找到两个互质的 d1d_1d2d_2 即可。

那么考虑线性筛预处理出每个数的最小质因子,把 aia_i 的最小质因子 pp 除光,剩下的数 xx 显然和 pp 互质,特判掉 x=1x=1 的情况即可。