AtCoder ABC 060 B – Choose Integers Python解説

2021年11月16日2021年11月21日

Choose Integers

あなたは、正の整数をいくつか選び、それらの総和を求めます。

選ぶ数の上限や、選ぶ整数の個数に制限はありません。
ただし、選ぶ数はすべて A の倍数でなくてはいけません。 また、少なくとも 1 つは整数を選ばなくてはいけません。

そして総和を B で割ったあまりが C となるようにしたいです。 こうなるように整数を選ぶことが出来るか判定してください。出来るならば YES、そうでないならば NO を出力してください。

AtCoder株式会社　AtCoder Beginner Contest 060

問題としては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")