EEH - Equation Equals Hazards
You are given the equation, GCD(A, M) = 1. You have to determine whether there exists at least one integer X such that A * X mod M = 1.
Input
Input starts with an integer T, denoting the number of test cases. Each test case contains two integers A and M.
Constraints
T <= 1000
1 <= A, M <= 1000000
Output
For each test case of input, print “Yes” if there exists at least one integer X such that A * X mod M = 1, print “No” otherwise.
Example
Input: 1 7 13 Output: Yes
Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology
Added by: | Alim |
Date: | 2016-04-01 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | Own Problem |