ABC解説

【pythonでABC182を解説】B - Almost GCD

問題概要

問題ページ

B - Almost GCD
B - Almost GCD

問題ページへ移動する

問題文

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

制約

  • \(1 \le N \le 100\)
  • \(2 \le A_i \le 1000\)
  • 入力は全て整数

問題の考察

B問題としてはコーディングが少し面倒な問題。

厳密には\(2\)からmax(\(A_1, A_2, A_3, \dots, A_N\))まででGCD度が最大なものを求めればいい。

しかし、制約が\(1 \le N \le 100\)、\(2 \le A_i \le 1000\)なので、\(2\)から(\1000\)までのうちGCD度が最大のものを求めても十分に間に合う。

ACコードではGCDの最大値をmxで保持しつつ、辞書型を使ってGCD度別のリストを作成している。（d[cnt] += [i]）

最後にGCD度がmxの内、最大の値を出力している。

たびすけ
たびすけ
GCD度が最大のものが全て計算した後でじゃないと分からないのがコーディングを面倒にしていますが、落ち着いてコーディング方針を決めてましょう！

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    mx = 0
    for i in range(2, 1001):
        cnt = 0
        for v in a:
            if v % i == 0:
                cnt += 1
        d[cnt] += [i]
        mx = max(mx, cnt)
    print(max(d[mx]))


if __name__ == '__main__':
    solve()

-ABC解説
-