ABC215 D - Coprime 2 - かんプリンの学習記録

問題概要
解説1
解説2
提出プログラム
感想

問題概要

長さ ${N}$ の正整数列 ${A}$ が与えられる．以下の条件を満たす ${1\leq k\leq M}$ をすべて求めよ．

すべての ${1\leq i\leq N}$ を満たす整数 ${i}$ について， ${\gcd(A_i,k)=1}$ である．

${1\leq N,M\leq 10^5\\ 1\leq A_i\leq 10^5}$

解説1

${\gcd(A_i,k)=1}$ となるのは， ${k}$ が ${A_i}$ の任意の素因数を持たないことと同じです． ${A}$ のすべての素因数を求めて，その素因数を持たない ${1}$ 以上 ${M}$ 以下の整数を求められれば良いです．
エラトステネスの篩を用いて， ${1}$ 以上 ${\max A}$ 以下の素数 ${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)}$ となります．

kanpurin.hatenablog.com

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)