[Python] エラトステネス ABC215D

ABC215D

これはABC215 D - Coprime 2を参考にした、自分用のメモである。

$gcd(A_i,k)=1$となるのは，$k$が$A_i$の任意の素因数を持たないことと同じです．$A$のすべての素因数を求めて，その素因数を持たない$1$以上$M$以下の整数を求められれば良いです．
エラトステネスの篩を用いて，$1$以上$maxA$以下の素数$p$であって，$p$を素因数に持つような$A_i$が存在するようなものを$O(\max A\log \log \max A)$で求めます．この素数$p$に対して，$1$以上$M$以下であって$p$の倍数であるような数を，同じくエラトステネスの篩の要領で消していけば残った数が答えとなります．全体の計算量は$O(N+\max A\log \log \max A+M\log \log M)$となります．

サンプルコード

N,M = map(int,input().split())
A = list(map(int,input().split()))
maxA = max(max(A),M)

k = [True] * (maxA+1) # iが条件を満たすkか(iが使えるか)
isprime = [True] * (maxA+1) # iが素数か
prime = [] # Aの素因数(使えない素数)
# Aの要素は使えない
for a in A: 
    k[a] = False
# エラトステネスの篩
for i in range(2,maxA+1):
    if not isprime[i]:
        continue
    for j in range(i*2,maxA+1,i):
        isprime[j] = False
        # iはjの素因数
        # jがAの要素ならiは使えない素数
        k[i] = k[i] and k[j]
    if not k[i]:
        prime.append(i)
# 使えない素数pに対して, pの倍数を使えなくする
for p in prime:
    for j in range(p*2,M+1,p):
        k[j] = k[j] and k[p]
# 使える数をansに入れる
ans = [1]
for i in range(2,M+1):
    if k[i]:
        ans.append(i)
# 出力
print(len(ans))
for i in ans:
    print(i)