問題概要

$A$ の倍数であって正の整数であるものをいくつか用意する。

その総和を $B$ で割った余りが $C$ となることはありうるか？

制約

$1 \le A, B \le 100$

考えたこと

まず、「いくつかの正の $A$ の倍数を足す」とあるが、 $A$ の倍数同士を足しても結局 $A$ の倍数であることに注意しよう。よって、問題は次のように言い換えられる。

$A$ の倍数を $B$ で割って $C$ 余ることはありうるか？

この問題へのアプローチはいくつか考えられる。

探索解法
整数論的考察

1. 探索解法

まず探索解法で解いてみる。基本的には、すべての $A$ の倍数を $B$ で割るのを試せばよいが、 $A$ の倍数は無限にあるので、実際にはすべての $A$ の倍数を試すことはできない。

そこで、次のことに着目しよう。実は、正の $A$ の倍数として最初の $B$ 個 ( $A, 2A, 3A, \dots, BA$ ) だけ試せば良いのだ。なぜならば、一般に

$(x + B)A \equiv xA \pmod B$

が成立するからだ。つまり、 $A, 2A, 3A, \dots$ を $B$ で割った余りは、周期 $B$ で同じことを繰り返すのだ。

よって、 $A, 2A, 3A, \dots BA$ を $B$ で割った余りの中に $C$ が含まれるかどうかを判定すればよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;

    bool res = false;
    for (int a = A; a <= A * B; a += A) {
        if (a % B == C) res = true;
    }
    cout << (res ? "YES" : "NO") << endl;
}

2. 整数論的考察

$A$ の倍数を $B$ で割った余りが $C$ になりうるかどうかは、

$Ax = By + C$

を満たす整数 $x, y$ が存在するかどうかを判定する問題であると言える。

これを変形して、

$Ax - By = C$

これを満たす整数 $x, y$ が存在する条件は、次のように書ける。

$\mathrm{gcd}(A, B) | C$

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;

    cout << (C % gcd(A, B) == 0 ? "YES" : "NO") << endl;
}