Yes or No (Editorial)

Solution

To transform $x$ into $y$ using only multiplication by integers z > 1, two primary conditions must be met:

1. $y$ must be divisible by $x$. If y \pmod x \neq 0, it is impossible to reach $y$ from $x$, so the answer is NO (unless x=y and k=0).

2. We must be able to decompose the ratio Q = y/x into exactly $k$ factors, where each factor is greater than $1$.

Let Q = y/x.

• If Q = 1 (i.e., x=y): We can only reach $y$ in k=0 operations. If k > 0, the answer is NO because every operation must multiply $x$ by at least 2, making the value strictly increase.

• If Q > 1:

  • The minimum number of operations is $1$ (by picking z = Q).

  • The maximum number of operations is the total number of prime factors of $Q$. Let this be $M$. For example, if Q = 12, the prime factors are 2 \times 2 \times 3, so M=3.

  • Any number of operations $k$ such that 1 \le k \le M is possible. This is because we can always take a set of $M$ factors and multiply any two of them together to reduce the count of factors by 1, until we reach a single factor $Q$.

The complexity per test case is O(\sqrt{y/x}) to find the prime factorization.

for _ in range(int(input())):
    x,y,k=map(int,input().split())
    if k==0:
        print("YES" if x==y else "NO")
        continue
    c=0
    i=2
    while i<=100000:
        c1=c2=0
        while x%i==0:
            x//=i
            c1+=1
        while y%i==0:
            y//=i
            c2+=1
        if c1>c2:
            c=-10**18
        c+=c2-c1
        i+=1
    print("YES" if c>=k else "NO")