AtCoder ABC 060 B – Choose Integers Python解説
Choose Integers
あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。
ただし、選ぶ数はすべて A の倍数でなくてはいけません。 また、少なくとも 1 つは整数を選ばなくてはいけません。そして総和を B で割ったあまりが C となるようにしたいです。 こうなるように整数を選ぶことが出来るか判定してください。出来るならば
AtCoder株式会社 AtCoder Beginner Contest 060YES
、そうでないならばNO
を出力してください。
問題としてはAの倍数をBで割り、余りがCになるか確認するだけの問題ですが、
整数の個数の選択がこちらに委ねられているため、問題の難しさがその分上がっている印象です。
問題文では整数を5000兆個選んでもよいとありますが、そこまで調べないといけないのでしょうか。
実は余りで出てくる数には周期があり、それ以上は繰り返しになります。
サンプルを作ってみると
a = 7
b = 4
for i in range(1, 20):
print(a * i, "%", b, "=", a * i % b)
#出力結果
7 % 4 = 3
14 % 4 = 2
21 % 4 = 1
28 % 4 = 0
35 % 4 = 3
42 % 4 = 2
49 % 4 = 1
56 % 4 = 0
63 % 4 = 3
70 % 4 = 2
77 % 4 = 1
84 % 4 = 0
91 % 4 = 3
98 % 4 = 2
105 % 4 = 1
112 % 4 = 0
119 % 4 = 3
126 % 4 = 2
133 % 4 = 1
Aの倍数ずつ増えていく場合は、B回ひとくくりでループします。
上記のように、7の倍数を4で割った場合、余りは3、2、1、0、3、2、1、0・・・と4回ごとループしていることが分かります。
ですので、この問題では、for文をBまでループさせて余りがCと一致するか確認すればよいです。
a, b, c = map(int, input().split())
flag = False
for i in range(1, b + 1):
if (a * i) % b == c:
flag = True
break
if flag:
print("YES")
else:
print("NO")