AtCoder ABC 182 B – Almost GCD Python解説

2021年12月29日

Almost GCD

数列 A (A1​,A2​,A3​,…,AN​) が与えられます。
正の整数 k の GCD 度を、A1​,A2​,A3​,…,AN​ のうち k で割り切れるものの数と定義します。
2 以上の整数のうち GCD 度が最大になるものを一つ求めてください。 GCD 度が最大のものが複数ある場合どれを出力しても構いません。

AtCoder Beginner Contest 「Almost GCD」

正の整数Kで配列Aの要素を割っていきます。整数Kは2からmax(A)までの数値を使い、総当たりで割り算をしていきます。割り切れる数は変数で数えていき、最後にGCD度が最大になるものを求めます。

n = int(input())
a = list(map(int, input().split()))

cnt = 0

for i in range(2, max(a) + 1):
    tmp = 0
    for j in a:
        if j % i == 0:
            tmp += 1
            if cnt <= tmp:
                cnt = tmp
                ans = i
                
print(ans)

for文を使って、2から配列の要素の最大値までループさせます。そして、for文の内側のループでは、配列aの要素がiで割り切れるときにtmp+1していきます。また、GCD度の値を更新したら、どの整数で値を更新することができたかを把握しておきたいので、ansに値を更新したときの整数を入れておきます。最後にansを出力して完了です。