Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.
Ivan the Terrible P36895
Given three integer numbers n, a and b, does there exist a natural t such that at ≡ b modn?
Input
Input consists of the number of cases c, followed by c triples with n, a and b. You can assume 2 ≤ n ≤ 109, 0 ≤ a < n, and 0 ≤ b < n. Additionally, assume c ≤ 200 for the “hard private test cases”.
Output
For each case, print “YES” or “NO” depending on whether at ≡ b modn has at least one solution t ≥ 0 or not.
Public test cases
Input
7 2 1 0 7 3 6 8 3 6 6 0 5 6 0 1 1000000000 42424242 1 1000000000 123456789 987654320
Output
NO YES NO NO YES YES NO
Information
- Author
- Ivan Geffner
- Language
- English
- Official solutions
- C++
- User solutions
- C++