AtCoder Beginner Contest 177에 가입했습니다

D 완. E 문제로 막혔으므로 복습으로 정리합니다.

E - Coprime

프로덕션 중에 생각한 것

실질 "pairwise coprime를 어떻게 판정할까?"라는 문제.
어리석게 pairwise로 판정하면 당연히 시간이 걸리므로 소수 기준으로 생각할 수밖에 없다.
요컨대 「모든 $A_i$에 대해 소인수가 전혀 쓰지 않는다」라고 하는 것이므로, $A_i$를 소인수 분해해 나온 것을 카운트(p_cnt[$A_i$]에 +1) 해 가면 좋을 것 같다.
예: 12→2・3, 16→2, 35→5・7이므로, 2가 2회 이상 있어 pairwise가 아니다
p_cnt의 최대값이 1이면 pairwise coprime, 최대값이 N이면 not coprime, 그렇지 않으면 setwise coprime.

다만 1을 포함하는 경우가 코너 케이스이므로, 우선 전부 1이라면 pairwise coprime.
1, 1, 3, 6과 같이 1 이외가 coprime가 아닌 경우 setwise coprime,
1, 1, 3, 4 같은 경우라면 pairwise coprime.
따라서 각 $A_i$에 대해 생각할 때, 그것이 1이면 개수를 카운트하지 않게 한다.

# Nの素因数分解を辞書で返す
def prime_fact(n):
    if n == 1:
        return {1: 1}

    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
        if n == 1:
            break
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = int(input())
    A = list(map(int, input().split()))

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    p_cnt = defaultdict(int) # 素因数pが出てきた回数を記録
    for a in A:
        if a == 1: continue # 1の個数は数えてもしょうがないので無視
        AP = prime_fact(a)
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    elif max_p == N:
        print("not coprime")
    else:
        print("setwise coprime")

1개(max_02.txt)만 TLE를 잡을 수 없다! ! 되어 타임업.

프로덕션 후에 생각한 것

C라면 어쨌든, Python(PyPy)에서는 $N$가 $10^6$도 있으면 힘들다.
여기서, 1,000,000 이하의 소수는 78,498 밖에 없는 것을 이용하는 것을 생각해 본다.
즉 $A_i$의 종류($len(set(A))$)가 대체로 8만 이상인 경우, 비둘기의 둥지 원리로부터 어딘가의 소인수에 반드시 커브가 발생해 pairwise coprime를 채우지 않게 된다! !
그래서 우선 적당히 gcd를 취해 not coprime의 케이스를 제외해 두고, 그다음에 8만 종류 이상 있는 케이스를 setwise coprime에 돌진하는 것으로, N을 실질 $10^6$에서 $10^5$정도까지 떨어뜨리는 것이 할 수 있다.

이 분기로 무사히 AC.

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if max(A) == 1:
        print("pairwise coprime")
        exit()

    # 全Aiの最大公約数が1より大きければnot coprime
    g = A[0]
    for a in A:
        g = math.gcd(g, a)
    if g > 1:
        print("not coprime")
        exit()

    # not coprimeでなく、Aが80000種類以上ならsetwise coprime
    SA = set(A)
    if len(SA) >= 80000:
        print("setwise coprime")
        exit()

    # 上記でないケースのみ頑張る
    p_cnt = defaultdict(int)
    cnt = 0
    for a in A:
        if a == 1: continue
        AP = prime_fact(a)
        for apk in AP.keys():
            p_cnt[apk] += 1

    max_p = max(p_cnt.values())
    if max_p == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

보다 강한 테스트 케이스에는 지는 생각이 들기 때문에 온순하게 해설의 고속화를 사용합시다.