ABC060B - Choose Integers

atcoder.jp

逆転の発想。(B * i + C) % A == 0 を満たす i が存在するかどうかを調べる。 A で割った余りは記録しておき、同じ余りが出現したら、見つからないと判断して終了。

using System;
using System.Collections.Generic;

namespace ABC060B
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var a = int.Parse(input[0]);
            var b = int.Parse(input[1]);
            var c = int.Parse(input[2]);
            var memo = new HashSet<int>();

            for (var i = 0; ; i++)
            {
                var modA = (b * i + c) % a;
                if (modA == 0)
                {
                    Console.WriteLine("YES");
                    return;
                }
                if (memo.Contains(modA))
                {
                    Console.WriteLine("NO");
                    return;
                }
                memo.Add(modA);
            }
        }
    }
}