AtCoder, ABC060: B. Choose Integers

まず問題文を読むと，「整数をいくつ選んでもよい」とある．
じゃあめんどくさいし１つだけ選ぶことにしましょう．
（２つ以上選んでも最終的には１つ選んだ場合の問題に帰着できる）

選んだ数を $a$ としてみましょう．
このとき， $a$ は $A$ の倍数です．
このため， $a$ は $k \in \mathbb{N}$ を用いて，
$\begin{align} a = k \cdot A \end{align}$
と表せます．この $a$ の定義を式1 とします．
問題文の条件が満たされるかどうかはこの $a$ が $C$ と $B$ を法として合同かどうかをチェックすればよいです．

次に， $a$ を $B$ で割った数の取りうる値について考えます．
そのために，まずは $a$ の最小値，最大値を考えてみます．
$a$ の取りうる数からなる数列を $\mathbf{X}$ とすると， $\mathbf{X}$ は
$\begin{align} \mathbf{X} = [ A, 2A, 3A, \dots] \end{align}$
と表せます．
$\mathbf{X}$ の要素を $B$ で割ったあまりは，数列を $\mathbf{X}^\prime$ として
$\begin{align} \mathbf{X}^\prime = [ A\%B, 2A\%B, 3A\%B, \dots] \end{align}$
となります．
この数列の最大値は $j$ を $B$ より小さい整数として， $j \cdot A$ です．
なぜなら， $j$ が $B$ に等しいなら ${X^\prime}_j = 0$ であり，
$j = B+i$ のときは ${X^\prime}_j \equiv {X^\prime}_i \text{ (mod $B$)}$ だからです．
つまり， $\mathbf{X}$ のはじめの $B-1$ 個の要素が $B$ で割った時に $C$ に等しくなるかどうかを確かめればよいということです．

雑に考えるとエイっとそれっぽいコードがかけそうだけど，ちゃんと自然言語で説明すると意外と難しい...？となった問題でした．
コードは↓です．

#include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    
    string ans = "NO";
    rep (i, a*b) {
        if (i*a % b == c) {
            ans = "YES";
            break;
        }
    }

    cout << ans << endl;
    return 0;
}