Multiplication and Division by 2
InterviewTime limit2sMemory limit512 MB
Given two uint32 values x and y, decide whether repeated multiplication by 2 mod 2^32 and floor division by 2 can turn x into y.
- Level
Medium5 of 10
- Topics
- Bit manipulation, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
Consider the number stored in the uint32 data type. We can multiply or divide it by any number of times in any order. Can we obtain the number after some sequence of operations?
When is stored in a uint32 and we multiply it by , it becomes . For example, , and .
When is stored in a uint32 and we divide it by , it becomes . For example, , and .
Input
The first line contains an integer , the number of test cases (). The next lines describe test cases, one per line. Each test case is given by two integers and ().
Output
For each test case, print a single word on a separate line: "Yes" if we can turn into using the allowed operations, or "No" otherwise.
Hint
In the first test case, we can multiply by , and then divide the result by to get .
In the second test case, there is no way to turn into .