ABC-060-B Choose Integers

■■■問題■■■

あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。
どんなに大きな整数を選んでもよいですし、整数を5000兆個選んでもよいです。
ただし、選ぶ数はすべてAの倍数でなくてはいけません。
また、少なくとも1つは整数を選ばなくてはいけません。

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

出来るならばYES、そうでないならばNOを出力してください。

■■■入力■■■

A B C

●1 <= A <= 100
●1 <= B <= 100
●0 <= C < B

■■■出力■■■

YESかNOを出力する。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7 5 1");
            //YES
            //たとえば7,14を選ぶと総和は21となり、
            //これを5で割ったあまりは1となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2 1");
            //NO
            //偶数をいくつ足したとしても、けっして奇数になることはありません
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 100 97");
            //YES
            //1の倍数、つまりすべての整数が選べるので、97を選べば良いです
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("40 98 58");
            //YES
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("77 42 36");
            //NO
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int A = wkArr[0];
        int B = wkArr[1];
        int C = wkArr[2];

        var ModSet = new HashSet<int>();
        int CurrMod = A;
        CurrMod %= B;
        while (true) {
            if (ModSet.Add(CurrMod) == false)
                break;
            CurrMod += A;
            CurrMod %= B;
        }
        Console.WriteLine(ModSet.Contains(C) ? "YES" : "NO");
    }
}

解説

等差数列
A 2*A 3*A 4*A 5*A ・・・
の各項を、Bを法とした余りとした、循環数列を作成してます。