ABC120-B - K-th Common Divisor を解く

ABC120-B - K-th Common Divisor

AもBも割り切れる数のうち、K番目の大きさのものを出力する問題

1から順に割れる数を挙げていって、K番目の約数が見つかったら

出力すればいい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
A,B,K=map(int,input().split())

# カウンタ（何番目に大きいか？）
c=0

for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0:
    c+=1

  # K番目に大きい割り切れる数が出たら終了
  if c==K:
    print(i)
    exit()

 

提出結果はWAでした。 …なんで？

問題文をもう一度読んでみる

＞ AもBも割り切る正整数のうち、K番目に大きいものを求めてください。

うーん、どうやら誤読していたっぽい

上記のコードは、小さい方からK番目に大きい数字を挙げていたが

この問題は大きい方からK番目に大きい数字を挙げる必要があるらしい

仕方ないので、AとBを割り切れる数を全て列挙して

大きい方からK番目の数を出力するコードに書き換えることにする

再提出したコード

# 入力
A,B,K=map(int,input().split())

# 割り切れた数を保存するリスト
l=[]

for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0:
    l.append(i)

# 出力
print(l[-K])

提出結果はACでした

いやー 誤読って怖いなあ