Так чи Ні (Розбір)

Розв'язання

Щоб перетворити $x$ на $y$, використовуючи лише множення на цілі числа z > 1, мають виконуватися дві основні умови:

1. $y$ має ділитися на $x$. Якщо y \pmod x \neq 0, досягти $y$ з $x$ неможливо, тому відповідь — NO (якщо тільки x=y і k=0).

2. Ми повинні мати можливість розкласти відношення Q = y/x рівно на $k$ множників, кожен з яких більший за $1$.

Нехай Q = y/x.

• Якщо Q = 1 (тобто x=y): ми можемо отримати $y$ лише за k=0 операцій. Якщо k > 0, відповідь — NO, оскільки кожна операція повинна множити $x$ щонайменше на 2, а отже значення буде строго зростати.

• Якщо Q > 1:

  • Мінімальна кількість операцій дорівнює $1$ (якщо вибрати z = Q).

  • Максимальна кількість операцій дорівнює загальній кількості простих множників числа $Q$. Позначимо її через $M$. Наприклад, якщо Q = 12, то прості множники — це 2 \times 2 \times 3, тому M=3.

  • Будь-яка кількість операцій $k$, така що 1 \le k \le M, є можливою. Це тому, що ми завжди можемо взяти набір із $M$ множників і перемножити будь-які два з них, щоб зменшити кількість множників на 1, доки не отримаємо один множник $Q$.

Складність для одного набору вхідних даних становить O(\sqrt{y/x}) для знаходження розкладу на прості множники.

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")