Ivan the Terrible P36895


Statement
 

pdf   zip

thehtml

Given three integer numbers n, a and b, does there exist a natural t such that atb 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 atb 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++