ABC393 - E - GCD of Subset
問題
$ iについて答えが$ x$ \iff①$ x \mid A_jであるような$ jが$ K個以上ある$ xのうち、②$ x \mid A_iを満たすものの最大値。
$ A_iの約数として$ xは何回現れるか？$ \iff$ xの倍数は$ Aのうちにいくつあるか？
$ T_x:=（$ 1 \leq x \leq max(A)=10^6）の各$ xについて、$ xの倍数は$ Aのうちにいくつあるか？
これが実は$ O(A_{\mathrm{max}}\mathrm{loglog}A_{\mathrm{max}})でできる。→素数ゼータ変換 $ S_i:= \left\{\begin{array}{ll}i & (T_i \geq K)\\ \mathrm{max}\{S_j \colon j \mid i \land j \neq i\} & (T_i < K)\end{array}\right.
$ Aのうちに倍数が$ K個以上ある数$ xについて、