---
title: "Codeforces Round 766 (Div. 2) D(枚舉+數論)"
tags: 題解, 枚舉, 數論
---

https://codeforces.com/contest/1627/problem/D

#### 題意

給一數列，每次能從中挑兩個數後將它們的 GCD 加入數列中，問最多能加入新數字多少次。

#### 思路

首先，能被加入的數字最大就是原數列的最大值，我們可以遍歷所有可能的數，檢查數列中是否有兩數的 GCD 等於當前的數，如果有則代表這個數可以被加入。

檢查時，我們只需要針對該數的倍數即可。

#### Code

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

    MAXN = max(A)
    seen = [False for _ in range(MAXN + 1)]
    for a in A:
        seen[a] = True

    ans = 0
    for v in range(1, MAXN + 1):
        if seen[v]: continue
        vs = [vv for vv in range(2 * v, MAXN + 1, v) if seen[vv]]
        if len(vs) < 2: continue
        g = vs[0]
        for vv in vs[1:]:
            g = gcd(g, vv)
            if g == v:
                ans += 1
                seen[v] = True
                break
    print(ans)

if __name__ == "__main__":
    solve()