From Rational to Binary Codechef Solution

by

From Rational to Binary Solution Problem Code: REALBIN

Chef and Divyam are playing a game. They start with a rational number XX, such that 0<X<10<X<1.

In each turn, Chef chooses a positive real number YY. Then Divyam either adds or subtracts YY to XX. So XX is replaced with either X+YX+Y or X−YX−Y. If this number becomes 00 or 11, then Chef wins. Otherwise, the game continues.

You are given XX, and you have to determine whether Chef can win in a finite number of moves. More formally, does there exist a finite number NN so that Chef has a strategy that is guaranteed to win in at most NN moves?

Here, XX will be given in the form ABAB, where AA and BB are positive integers, A<BA<B and gcd(A,B)=1gcd(A,B)=1.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers AA and BB.

Output

For each test case, print a single line containing the string "Yes" if Chef can win the game in a finite number of moves and "No" otherwise (without quotes). You can print "Yes" or "No" in any case.

Constraints

  • 1≤T≤1061≤T≤106
  • 1≤A<B≤10181≤A<B≤1018
  • gcd(A,B)=1gcd(A,B)=1

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input

2
1 2
2 3

Sample Output

Yes
No

Explanation

Test case 1: Chef will choose Y=12Y=12, so whatever Divyam does, the number will become 00 or 11. Hence Chef will win in a finite number of moves.

Test case 2: No matter what Chef chooses, it can be shown that Divyam can make sure Chef never wins.

Program:

import io, os, time,sys

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
tests=int(input())
for _ in range(tests):
    
    a,b=map(int,input().split())
    
    if b&(b-1)==0:
        sys.stdout.write("Yes\n")
    else:
        sys.stdout.write("No\n")

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

fifteen − thirteen =