[AtCoder]ABC B060 – Choose Integers[C++]

引き続き、過去問をC++でB問題を解いていきます。

ABC B060 – Choose Integers

問題

あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。 どんなに大きな整数を選んでもよいですし、整数を5000兆個選んでもよいです。 ただし、選ぶ数はすべてAの倍数でなくてはいけません。 また、少なくとも1つは整数を選ばなくてはいけません。
そして総和をBで割ったあまりが CC となるようにしたいです。 こうなるように整数を選ぶことが出来るか判定してください。
出来るならばYES、そうでないならばNOを出力してください。

自分の回答

#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int A, B, C;
  cin >> A >> B >> C;
 
  for(int i = 1; i < B; i++){
    if(A * i % B == C){
    cout << "YES" << endl;
    exit(0);
    }
  }
  cout << "NO" << endl;
}

if文の条件のA * i % B == Cはすぐに思いつくと思います。何を選ぼうがAの倍数になるので、破られる側の値はA*iと表すことができます。それに対して、Bで割ったあまりがCになるかどうかを確認すればいいです。
問題はforの条件のi < Bの部分ではないでしょうか。何故、iがB未満であれば十分なのでしょうか。それは、A * i % Bの値(A*iをBで割った余り)はB個が一塊りの数値の繰り返しになるからです。言葉だけだとわかりづらいので、下記に例を載せました。

A = 1, B = 5の時、
1%5=1
2%5=2
3%5=3
4%5=4
5%5=0
6%5=1
7%5=2
8%5=3
9%5=4
10%5=0
とこのように余りの値がB=5個一括りの数列になっていることがわかると思います。

A = 3, B = 4の時、
3%4=3
6%4=2
9%4=1
12%4=0
15%4=3
18%4=2
21%4=1
24%4=0
27%4=3
30%4=2
同じように余りが、B=4個一括りの数列になっています。