AtCoder ABC 182 B – Almost GCD Python解説
Almost GCD
数列 A (A1,A2,A3,…,AN) が与えられます。
AtCoder Beginner Contest 「Almost GCD」
正の整数 k の GCD 度を、A1,A2,A3,…,AN のうち k で割り切れるものの数と定義します。
2 以上の整数のうち GCD 度が最大になるものを一つ求めてください。 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を出力して完了です。