AtCoder ABC 120 B – K-th Common Divisor Python解説

スポンサーリンク

K-th Common Divisor

正整数 A, B が与えられます。

A も B も割り切る正整数のうち、K 番目に大きいものを求めてください。
なお、与えられる入力では、A も B も割り切る正整数のうち K 番目に大きいものが存在することが保証されます。

AtCoder Beginner Contest 「K-th Common Divisor」

やる事はAもBも割り切れる整数の列挙と、割り切れる整数の中でK番目に大きい整数を答えることの2つです。

a, b, k = map(int, input().split())

c = []

for i in range(1, max(a, b) + 1):
    if a % i == 0 and b % i == 0:
        c.append(i)
        
print(c[-k])

入力からa,b,kを受け取ったら割り切れる整数を確認していきます。aもbも割り切れた際は、その数値を配列に追加したいので配列cを用意しました。

for文では0は割り切れる整数に入らないので1から始めるようにし、aとbの数値の大きい方までループを回します。
割り切れた数値を配列に入れたら、最後に数値を出力します。配列は昇順に並んでいるので配列cの-kを出力して完了です。