逆転の発想。(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); } } } }