Bəli və ya Xeyr (Həll təhlili)

Həll

z > 1 olan tam ədədlərə vurma əməliyyatından istifadə edərək $x$-i $y$-ə çevirmək üçün iki əsas şərt ödənməlidir:

1. $y$, $x$-ə bölünməlidir. Əgər y \pmod x \neq 0 olarsa, onda $x$-dən $y$-ə çatmaq mümkün deyil, buna görə cavab NO-dur (x=y və k=0 halı istisna olmaqla).

2. Q = y/x nisbətini hər biri $1$-dən böyük olan dəqiq $k$ vuruğa ayıra bilməliyik.

Qoy Q = y/x olsun.

• Əgər Q = 1-dirsə (yəni x=y): Biz yalnız k=0 əməliyyatda $y$-ə çata bilərik. Əgər k > 0 olarsa, cavab NO-dur, çünki hər əməliyyatda $x$ ən azı 2-yə vurulmalıdır və bu da qiymətin ciddi şəkildə artmasına səbəb olur.

• Əgər Q > 1-dirsə:

  • Əməliyyatların minimum sayı $1$-dir (z = Q seçməklə).

  • Əməliyyatların maksimum sayı $Q$-nun sadə vuruqlarının ümumi sayıdır. Bunu $M$ ilə işarə edək. Məsələn, əgər Q = 12 olarsa, sadə vuruqlar 2 \times 2 \times 3 olar, deməli M=3.

  • 1 \le k \le M şərtini ödəyən istənilən $k$ əməliyyat sayı mümkündür. Bunun səbəbi odur ki, biz həmişə $M$ vuruqdan ibarət bir çoxluq götürə və onların istənilən ikisini bir-birinə vuraraq vuruqların sayını 1 azalda bilərik; bu prosesi tək bir $Q$ vuruğu qalana qədər davam etdirmək olar.

Hər bir giriş verilənləri dəsti üçün mürəkkəblik sadə vuruqlara ayırmanı tapmaq üçün O(\sqrt{y/x})-dir.

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