CF1366D Two Divisors 做题记录

给定 $n$ 个数 $a_1,a_2,\dots ,a_n$。

对于每一个 $a_i$ 求出它的两个不为 $1$ 的约数 $d_1,d_2$ ，满足 $\gcd(d_1 + d_2, a_i) = 1$，或指出不存在这样的 $d_1,d_2$。

$n\leq 5\times 10^5$，$2\le a_i\le 10^7$

大力推一波式子：

设 $\gcd(d_1,d_2)=d$，$d_1'=d_1/d,d_2'=d_2/d$。

那么 $d_1+d_2=d(d_1'+d_2')$，$\gcd(d_1+d_2,a_i)=\gcd(d(d_1'+d_2'),a_i)=1$。

由于 $d$ 一定是 $a_i$ 的因子，所以 $\gcd(d(d_1',d_2'),a_i)\ge d$，所以 $d$ 只能为 $1$。

也就是说，找到两个互质的 $d_1$ 和 $d_2$ 即可。

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