AtCoderBeginnerContest177復習＆まとめ（後半）

# AtCoder ABC177
2020-08-29(土)に行われたAtCoderBeginnerContest177の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．[前半はこちら](https://qiita.com/takaito0423/items/a74898cc43d14e6ced62)
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
[コンテストページはこちら](https://atcoder.jp/contests/abc177)
[公式解説PDF](https://atcoder.jp/contests/abc177/editorial)

## D問題　Friends
> 問題文
> 人$1$から人$N$までの$N$人の人がいます。
> 「人$A_i$と人$B_i$は友達である」という情報が$M$個与えられます。同じ情報が複数回与えられることもあります。
> $X$と$Y$が友達、かつ、$Y$と$Z$が友達ならば、$X$と$Z$も友達です。また、$M$個の情報から導くことができない友達関係は存在しません。
> 悪の高橋君は、この$N$人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。
> 最小でいくつのグループに分ければ良いでしょうか？

友達の繋がりをたどって，何人と繋がりがあるのか（＝公式解説の友達集合の要素数）を，各まとまりごとに調べていく．
友達同士を同じグループに入れないようにするためには，少なくとも一番大きい友達集合の要素数のグループが必要となり，それが出力すべき答えとなる．
実装は，人$1$から人$N$がどこかのグループに属しているかどうか確認するlistを作成して管理することで，計算の重複をしないようにしている．

```python:abc177d.py
n, m = map(int, input().split())
set_dict = {}
chech_list = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    if a in set_dict:
        set_dict[a].add(b)
    else:
        set_dict[a] = {b}
    if b in set_dict:
        set_dict[b].add(a)
    else:
        set_dict[b] = {a}
    chech_list[a] = 1
    chech_list[b] = 1
ans = 1
for i in range(1, n + 1):
    if chech_list[i] == 0:
        continue
    count = 0
    temp_set = set_dict[i]
    while len(temp_set) > 0:
        x = temp_set.pop()
        count += 1
        chech_list[x] = 0
        for y in set_dict[x]:
            if chech_list[y] == 1:
                temp_set.add(y)
    ans = max(count, ans)
print(ans)
```

## 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,…,A_N)=1$であるとき、{$A_i$}は setwise coprime であるといいます。
> {$A_i$}が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。
> ただし$GCD(…)$は最大公約数を表します。

素因数分解を高速でする方法が思いつかなかった．
公式解説のエラトステネスの篩みて納得．

```python:abc177e.py
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break
if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
```

後半も最後まで読んでいただきありがとうございました．