【ABC182 B】「Almost GCD」を解く【Python3】

与えられた数列Aのうち、正の整数kで割り切れるものの数を「正の整数kのGCD度」としたとき、2以上の整数のうち、GCD度が最大になるものを一つ求める問題です。

提出

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

m = max(a)+1
gcd = 0

for i in range(2,m):
    tmp = 0
    for j in a:
        if i > j:
            continue
        if j%i == 0:
            tmp += 1
    if gcd < tmp:
        gcd = tmp
        ans = i

print(ans)

GCD度が最大になるものが複数ある場合、どれを出力しても正解とのこと。

入力はすべて整数です。数列Aはリストにしておきます。

for文を用いて、2以上からリスト内の最大数までのGCD度を調べていきます。

毎回、「tmp = 0」とし、リストaの中で整数kで割り切れる数をカウントします。

数え終わったときに「gcd < tmp」であれば、gcdにtmpを代入し、その時の整数k(=i)を「ans」に入れます。最終的に「ans」に入っているものが答えになるので、これを出力します。