ABC177 E

問題: atcoder.jp
本番提出: https://atcoder.jp/contests/abc177/submissions/16355934

エラトステネスの篩でいい感じにsetwise coprime, pairwise coprime, not coprimeを判定したいです。

not coprimeは「ある素数ですべてのAが割り切れる」であり、pairwise coprimeとは、「任意の素数で割れるAは高々1個」であり、setwise coprimeは「not coprimeではない」かつ「ある素数で割れるAが2個以上ある」であることがわかるので、長さ1000001の配列にAとして出てきた個数を数えて、エラトステネスの篩をしながら割れたAの個数を求めれば一度に判定ができます。

このとき、A=1の個数は条件判定に影響を及ぼしません。A=1があるとき無条件でnot coprimeは成立せず、pairwiseかsetwiseかの判定ですが、上に書いた条件が保たれています。

本番でミスした点は、「ある素数で割れるAが2個以上あり全部ではない」をsetwise coprimeだと思ってしまったことで、これは6, 9, 12の場合に2で6と12が割れるからsetwise coprime！みたいなことをしてしまいました。それより大きい素数で全部割れる可能性があるのでフラグだけ立てて最後に判定すればよいです。

例
A=[3,4,5]
Nums = [0,0,0,1,1,1,0,0, ...]
Primes = [1,1,1,1,1,1,1, ...]（Primes[n]=0ならnは素数でない）

p=2
num = Nums[2]+Nums[4]+ ... = 1
Primes = [1,1,(1),1,0,1,0,...]
p=3
num = Nums[3]+Nums[6]+... = 1
Primes = [1,1,1,(1),0,1,0,...]
p=5
num = Nums[5]+Nums[10]+... = 1
Primes = [1,1,1,1,0,(1),0,...]
p=7
num = Nums[7]+Nums[14]+... = 0
...

numは一度も2以上にならなかったのでpairwise coprimeです。

計算量はO(max(N) loglog max(N)), max(N)=10^6で間に合います