Edit

【pythonでABC177を解説】E - Coprime

問題概要

問題ページ

問題文

\(N\) 個の整数があります。\(i\) 番目の数は \(A_i\) です。

「全ての \(1\leq i < j \leq N\) について、\(GCD(A_i,A_j)=1\)」が成り立つとき、\(\{A_i\}\) は pairwise coprime であるといいます。

\(\{A_i\}\) が pairwise coprime ではなく、かつ、\(GCD(A_1,\ldots,A_N)=1\) であるとき、\(\{A_i\}\) は setwise coprime であるといいます。

\(\{A_i\}\) が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。

ただし \(GCD(\ldots)\) は最大公約数を表します。

制約

  • \(2 \leq N \leq 10^6\)
  • \(1 \leq A_i\leq 10^6\)

問題の考察

ACコード

import sys
import math
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = sorted(list(map(int, input().rstrip('\n').split())), reverse=True)
    mx = a[0]
    prime = [True] * (mx + 1)
    prime_l = []

    for i in range(2, mx + 1):
        if prime[i]:
            prime_l.append(i)
            for j in range(i, mx + 1, i):
                prime[j] = False

    is_p = True
    fac = collections.defaultdict(int)
    for v in a:
        for p_v in prime_l:
            if p_v > int(v ** 0.5):
                break
            if v % p_v == 0:
                if p_v not in fac:
                    fac[p_v]
                    while v % p_v == 0:
                        v //= p_v
                else:
                    is_p = False
                    break
        if v != 1:
            if v not in fac:
                fac[v]
            else:
                is_p = False
                break
        if not is_p:
            break

    if is_p:
        print("pairwise coprime")
    else:
        gcd = a[0]
        for i in range(1, n):
            gcd = math.gcd(gcd, a[i])
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")


if __name__ == '__main__':
    solve()

プログラミング

-Edit
-