Gold Rush (Codeforces 1829D)
Tags: Implement, dfs and similar

Initially you have a single pile with $$$n$$$ gold nuggets. In an operation you can do the following:   Take any pile and split it into two piles, so that one of the resulting piles has exactly twice as many gold nuggets as the other. (All piles should have an integer number of nuggets.)   One possible move is to take a pile of size $$$6$$$ and split it into piles of sizes $$$2$$$ and $$$4$$$, which is valid since $$$4$$$ is twice as large as $$$2$$$.  Can you make a pile with exactly $$$m$$$ gold nuggets using zero or more operations?

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^7$$$) — the starting and target pile sizes, respectively.

Output: For each test case, output "YES" if you can make a pile of size exactly $$$m$$$, and "NO" otherwise.You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

Note: The first test case is pictured in the statement. We can make a pile of size $$$4$$$.In the second test case, we can perform the following operations: $$$\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$$$. The pile that is split apart is colored red before each operation.In the third test case, we can't perform a single operation.In the fourth test case, we can't end up with a larger pile than we started with.

Sample Inputs:
11
6 4
9 4
4 2
18 27
27 4
27 2
27 10
1 1
3 1
5 1
746001 2984004

Sample Outputs:
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
input = sys.stdin.readline

def read_str():
    return input().rstrip()

def read_int():
    return int(input().rstrip())

def read_lst():
    return list(map(int, input().rstrip().split()))

def read_map():
    return map(int, input().rstrip().split())

def ok(b):
    print('YES' if b else 'NO')
mem = {}

def ck(n, m):
    if n == m:
        return True
    elif n % 3 != 0:
        return False
    elif (n, m) in mem:
        return mem[n, m]
    else:
        result = ck(n // 3, m) or ck(n // 3 * 2, m)
        mem[n, m] = result
        return result

def solve():
    (n, m) = read_map()
    ok(ck(n, m))
if __name__ == '__main__':
    for _ in range(read_int()):
        solve()

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    a = 'YES'
    k = 0
    while n != m:
        if n % 3 == 0:
            n //= 3
            k += 1
        elif m != n:
            a = 'NO'
            break
        if n < m:
            while k > 0 and n < m:
                n *= 2
                k -= 1
    print(a)

Solution (Python):
t = int(input())
dict = {}

def check(a, b):
    if a == b:
        return True
    if a % 3 != 0:
        return False
    if (a, b) in dict:
        return dict[a, b]
    ans = check(a // 3, b) or check(2 * a // 3, b)
    dict[a, b] = ans
    return ans
while t > 0:
    t -= 1
    word = [int(a) for a in input().split()]
    n = word[0]
    m = word[1]
    helper = [n]
    if check(n, m):
        print('YES')
    else:
        print('NO')