TWOGAME - Two Game
Alice started playing a new simple game. She starts with the pair of integers (1, 1) and then she may a) duplicate one of the numbers or b) subtract the smaller number from the bigger one. So the game may proceed as follows: she starts with (1, 1), then she moves to (2, 1), then to (4, 1), then to (4, 2), then to (8, 2), then to (6, 2), etc.
She is now wondering if given an arbitrary pair of positive integers (A, B), will she be able to reach at this pair using the proceduce described above ?
The first line contains a single positive integer T (T ≤ 500), denoting the number of test cases to solve. Each test case consists of a single line containing two positive integers A, B (A, B ≤ 1018).
For each test case print a single line with the character Y if it is possible for Alice to reach the given pair or N if it is impossible.
3 3 Output: Y
Seemed hard at first, then almost too simple, then again almost impossible given the constraints, then got AC. Nice one =)
Raghav Aggiwal Again:
Nice one :) ....
Beautiful Logic.....just generalise the numbers....
Nice problem... Made me think
@anurag Start with (1, 1) then -> (1, 2) -> (1, 4) -> (2, 4) -> (4, 4) (we only used duplications).Last edit: 2014-02-11 16:19:06
I guess weak test cases I think for 4 4 ans should be no but my AC soln gives Yes
try some test cases on you own and you will find the method to solve it...:)
after a long time used something new logic
use long long