Another Problem About Dividing Numbers (Codeforces 1538D)
Tags: Math, number theory

You are given two integers $$$a$$$ and $$$b$$$. In one turn, you can do one of the following operations:   Take an integer $$$c$$$ ($$$c > 1$$$ and $$$a$$$ should be divisible by $$$c$$$) and replace $$$a$$$ with $$$\frac{a}{c}$$$;  Take an integer $$$c$$$ ($$$c > 1$$$ and $$$b$$$ should be divisible by $$$c$$$) and replace $$$b$$$ with $$$\frac{b}{c}$$$. Your goal is to make $$$a$$$ equal to $$$b$$$ using exactly $$$k$$$ turns.For example, the numbers $$$a=36$$$ and $$$b=48$$$ can be made equal in $$$4$$$ moves:   $$$c=6$$$, divide $$$b$$$ by $$$c$$$ $$$\Rightarrow$$$ $$$a=36$$$, $$$b=8$$$;  $$$c=2$$$, divide $$$a$$$ by $$$c$$$ $$$\Rightarrow$$$ $$$a=18$$$, $$$b=8$$$;  $$$c=9$$$, divide $$$a$$$ by $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$, $$$b=8$$$;  $$$c=4$$$, divide $$$b$$$ by $$$c$$$ $$$\Rightarrow$$$ $$$a=2$$$, $$$b=2$$$. For the given numbers $$$a$$$ and $$$b$$$, determine whether it is possible to make them equal using exactly $$$k$$$ turns.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.Each test case is contains three integers $$$a$$$, $$$b$$$ and $$$k$$$ ($$$1 \le a, b, k \le 10^9$$$).

Output: For each test case output:   "Yes", if it is possible to make the numbers $$$a$$$ and $$$b$$$ equal in exactly $$$k$$$ turns;  "No" otherwise. The strings "Yes" and "No" can be output in any case.


Sample Inputs:
8
36 48 2
36 48 3
36 48 4
2 8 1
2 8 2
1000000000 1000000000 1000000000
1 2 1
2 2 1

Sample Outputs:
YES
YES
YES
YES
YES
NO
YES
NO

Solution (Python):
def naiveSolve():
    return
maxN = int(pow(1000000000.0, 0.5)) + 5
sieve = [1] * maxN
primes = []
for i in range(2, maxN):
    if sieve[i] == 1:
        primes.append(i)
        for j in range(2 * i, maxN, i):
            sieve[j] = 0

def pdc(x):
    cnt = 0
    for p in primes:
        while x % p == 0:
            cnt += 1
            x //= p
    if x > 1:
        cnt += 1
    return cnt

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (a, b, k) = readIntArr()
        if a < b:
            temp = a
            a = b
            b = temp
        if k == 1:
            if a > b and a % b == 0:
                allans.append('Yes')
            else:
                allans.append('No')
        else:
            maxK = pdc(a) + pdc(b)
            if k <= maxK:
                allans.append('Yes')
            else:
                allans.append('No')
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
    print('? {} {}'.format(i, j))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(' '.join([str(x) for x in ans])))
    sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
    main()

Solution (Python):
import sys

def sieve(n):
    primes = set(range(2, n + 1))
    for i in range(2, int(n ** 0.5 + 1)):
        primes.difference_update(range(i * 2, n + 1, i))
    return list(primes)
input = sys.stdin.readline

def main():
    primes = sieve(int(10 ** 4.5))
    for _ in range(int(input())):
        (a, b, k) = map(int, input().split())
        if k == 1:
            print(a != b and (a % b == 0 or b % a == 0) and 'YES' or 'NO')
            continue
        c0 = 0
        for p in primes:
            if p * p > a:
                break
            while a % p == 0:
                a //= p
                c0 += 1
        if a > 1:
            c0 += 1
        c1 = 0
        for p in primes:
            if p * p > b:
                break
            while b % p == 0:
                b //= p
                c1 += 1
        if b > 1:
            c1 += 1
        print(k <= c0 + c1 and 'YES' or 'NO')
main()

Solution (Python):
from sys import setrecursionlimit, stdin, stderr
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
from itertools import combinations, permutations, product
from functools import lru_cache, cmp_to_key, reduce
from heapq import heapify, heappush, heappop, heappushpop, heapreplace
setrecursionlimit(300005)
LOGN = 20
INF = 1 << 60
MOD = 10 ** 9 + 7
input = lambda : stdin.readline().rstrip('\r\n')
dbg = lambda *A, **M: stderr.write('\x1b[91m' + M.get('sep', ' ').join(map(str, A)) + M.get('end', '\n') + '\x1b[0m')

def sieve(n):
    is_prime = [True for _ in range(n + 1)]
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    primes = [i for (i, flag) in enumerate(is_prime) if flag]
    return (primes, is_prime)

def solve():
    (primes, _) = sieve(31625)
    for _ in range(int(input())):
        (A, B, K) = map(int, input().split())
        if K == 1:
            if A == B:
                print('NO')
            elif A % B == 0 or B % A == 0:
                print('YES')
            else:
                print('NO')
            continue
        nA = 0
        for prime in primes:
            while A % prime == 0:
                nA += 1
                A //= prime
            if A == 1:
                break
        nA += int(A != 1)
        nB = 0
        for prime in primes:
            while B % prime == 0:
                nB += 1
                B //= prime
            if B == 1:
                break
        nB += int(B != 1)
        print('YES' if K <= nA + nB else 'NO')
if __name__ == '__main__':
    solve()