考えて競プロする

プログラミングコンテストの問題をどう考えて解いたかを記録していくブログです。使用言語はPython3

ABC060-B - Choose Integers を解く(2)

ABC-B

ABC060-B - Choose Integers を解く(1) の続き

 

余りの出現パターンはループするのでは？ という推測が立ったので

その推測が成り立つ前提で考察を進めていく

 

ループするとなると、2周目以降を調べる必要がなくなるので

1周目までの余りの中に答えがあれば 'YES'、なければ 'NO' とすればいい

 

ループしたことを判定するためには、余りの出現回数を保存しておく必要がある

割る数である B の範囲が 1 <= B <= 100 であるので

この大きさのリストを用意しておけばいいだろう

 

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

 
提出したコード
# 入力
A,B,C=map(int,input().split())

# 余りの出現回数を保存する配列
l=[0]*100

# Aに掛ける係数
t=1

while True:
  # 余りを求める
  x=t*A%B

  # 余りがCと一致したら終了
  if x==C:
    print('YES')
    exit()

  # 余りが2回以上出現したら終了
  elif l[x]>0:
    print('NO')
    exit()

  # 余りの出現回数をインクリメント
  else:
    l[x]+=1

  # Aに掛ける係数を+1する（次のAの倍数へ）
  t+=1
 

提出結果はACでした

 

解説PDFには余りがループすることの証明が書いてあったので

気になる人は読んでみてください