ABC177 E - Coprime
問題概要
個の整数からなる集合{
}が，pairwise coprime，setwise coprime，もしくはnot coprimeであるか判定せよ．
pairwise coprimeとは，
について
が成り立つときのこととする．setwise coprimeとは，pairwise coprimeでない，かつ
が成り立つときのこととする．どちらでもないとき，not coprimeとする．
解法
まず，全体のGCDを取り，それが1でなければnot coprimeとする．全体のGCDが1でなければ，setwise coprimeでないし，pairwise coprimeなら全体のGCDは1になるので，pairwise coprimeでもないからである．
次に，pairwise coprimeでないかを判定したい．pairwise coprimeでなければ，ある1つのが1でないはずである．これは，ある
が1より大きい公約数を持つことを意味する．そこで，各整数
を素因数分解して，どれか一つでも素因数が被っているようなら，ある
が1より大きい公約数を持つことに気がつく．
よって，個の整数
を高速に素因数分解したい．前処理なしである一つの整数
を計算量
で素因数分解する方法は，けんちょんさんの記事などに書かれていて有名である．ただし今回それを用いると，
かかってしまい，間に合わない1．
そこでosa_k法を用いる．これを用いると，素因数分解したい最大の整数をとしたとき，前処理
で，素因数分解クエリ
ができる．
前処理はエラトステネスの篩2をしながら，各整数を割り切る最小の素因数を求める．素因数分解は，nを割り切る最小の素因数で割り，nをその割った結果で置き換えながら，nが1になるまで割り続けることでできる．
あとは，各整数を素因数分解し，出てくる素因数が被っていないかチェックする．被りのチェックは，(Aの最大要素 + 1)の長さの配列を用意しておき，それぞれの整数の素因数ごとに1を足していき，配列の最大値が1以下か確認するなどでできる．
コード
def main():
from math import gcd
_ = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
def Eratosthenes(sup: int) -> set:
primes = [True]*(sup+1)
primes[0] = False
primes[1] = False
for i in range(2, sup+1):
if primes[i]:
MINFact[i] = i
mul = 2
while i*mul <= sup:
primes[i*mul] = False
if MINFact[i*mul] == -1:
MINFact[i*mul] = i
mul += 1
def prime_factor(n):
while n != 1:
prime = MINFact[n]
while MINFact[n] == prime:
n //= prime
B[prime] += 1
MINFact = [-1] * (maxA + 1)
MINFact[0] = 0
MINFact[1] = 1
Eratosthenes(maxA)
g = A[0]
for a in A:
g = gcd(g, a)
B = [0]*(maxA+1)
for a in A:
prime_factor(a)
if g != 1:
print("not coprime")
elif max(B) <= 1:
print("pairwise coprime")
else:
print("setwise coprime")
if __name__ == '__main__':
main()
コンテスト中は「素因数分解 高速」とかでググって，なんとか実装した．
以下，参考にしました．
・エラトステネスの篩の要領で1<=i<=10^6の各iについて「iの最小の素因数」を記録しておきます
— 十六夜 龍 (@Izayoi_R_sakura) 2020年8月29日
・素因数分解のときは配列を参照してO(1)で素因数が1つ分かります。その素因数をpとして、i/pのもつ素因数も配列に既に記録されています
・素因数がO(1)で求まるので素因数分解をO(log N)で出来ます
また，106以下の素数が78498個しかないことから，1以外の数がこれより多ければpairwiseにはならないというツイートを見た．1以外の数がこれ以下ならの素因数分解をしても，実行時間は2secに収まる．え，すげー．
提出コードへのリンクコード
def main():
from math import gcd
_ = int(input())
A = [int(i) for i in input().split()]
def prime_factorize(n):
for i in range(2, n+1):
if i*i > n:
break
if n % i != 0:
continue
while n % i == 0:
n //= i
B[i] += 1
if n != 1:
B[n] += 1
# 10**6 以下の素数は78498個しかない
# よって，1以外の数がこれより多ければpairwiseにはならない
check = True if sum(a != 1 for a in A) <= 80000 else False
maxA = max(A)
B = [0] * (maxA + 1)
if check:
for a in A:
prime_factorize(a)
g = A[0]
for a in A:
g = gcd(g, a)
if g != 1:
print("not coprime")
elif check and max(B) <= 1:
print("pairwise coprime")
else:
print("setwise coprime")
if __name__ == '__main__':
main()
