Madoka and the Best School in Russia (Codeforces 1647D)
Tags: Math, number theory

Madoka is going to enroll in "TSUNS PTU". But she stumbled upon a difficult task during the entrance computer science exam:  A number is called good if it is a multiple of $$$d$$$.  A number is called beatiful if it is good and it cannot be represented as a product of two good numbers. Notice that a beautiful number must be good.Given a good number $$$x$$$, determine whether it can be represented in at least two different ways as a product of several (possibly, one) beautiful numbers. Two ways are different if the sets of numbers used are different.Solve this problem for Madoka and help her to enroll in the best school in Russia!

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — number of test cases. Below comes their description.Each test case consists of two integers $$$x$$$ and $$$d$$$, separated by a space ($$$2 \leq x, d \leq 10^9$$$). It is guaranteed that $$$x$$$ is a multiple of $$$d$$$.

Output: For each set of input data, output "NO" if the number cannot be represented in at least two ways. Otherwise, output "YES".You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

Note: In the first example, $$$6$$$ can be represented as $$$6$$$, $$$1 \cdot 6$$$, $$$2 \cdot 3$$$. But $$$3$$$ and $$$1$$$ are not a good numbers because they are not divisible by $$$2$$$, so there is only one way.In the second example, $$$12$$$ can be represented as $$$6 \cdot 2$$$, $$$12$$$, $$$3 \cdot 4$$$, or $$$3 \cdot 2 \cdot 2$$$. The first option is suitable. The second is— no, because $$$12$$$ is not beautiful number ($$$12 = 6 \cdot 2$$$). The third and fourth are also not suitable, because $$$3$$$ is not good number.In the third example, $$$36$$$ can be represented as $$$18 \cdot 2$$$ and $$$6 \cdot 6$$$. Therefore it can be decomposed in at least two ways.

Sample Inputs:
8
6 2
12 2
36 2
8 2
1000 10
2376 6
128 4
16384 4

Sample Outputs:
NO
NO
YES
NO
YES
YES
NO
YES

Solution (Python):
def isPrime(n):
    if n == 1:
        return True
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def factor(n):
    ans = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            ans.append(n // i)
    return ans
for lkdl in range(int(input())):
    (x, d) = map(int, input().split())
    c = 0
    while x % d == 0:
        x = x // d
        c += 1
    if c == 1:
        print('NO')
    elif isPrime(x):
        if isPrime(d):
            print('NO')
        elif c == 2:
            print('NO')
        elif c >= 4:
            print('YES')
        else:
            f = factor(d)
            ans = 'NO'
            for i in f:
                if i * d * x % (d * d) != 0:
                    ans = 'YES'
                    break
            print(ans)
    else:
        print('YES')

Solution (Python):
from sys import stdin
import math
from collections import deque
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
input = stdin.readline

def ceil(m, n):
    val = m // n
    if m % n != 0:
        return val + 1
    return val

def isprime(v):
    if v == 1:
        return True
    for i in range(2, int(math.sqrt(v)) + 1):
        if v % i == 0:
            return False
    return True
for _ in range(int(input())):
    (x, d) = map(int, input().split())
    (temp, times) = (x, 0)
    while temp % d == 0:
        times += 1
        temp //= d
    if times <= 1:
        print('NO')
        continue
    if times == 2:
        if not isprime(temp):
            print('YES')
        else:
            print('NO')
        continue
    if not isprime(temp):
        print('YES')
    elif isprime(d):
        print('NO')
    elif d == temp ** 2 and times == 3:
        print('NO')
    else:
        print('YES')

Solution (Python):
from math import sqrt

def primeCheck(n):
    t = 0
    if n == 1:
        return True
    if n > 1:
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                t = 1
                break
        if t == 0:
            return True
        else:
            return False
    else:
        return False
T = int(input())
for t in range(T):
    (x, d) = map(int, input().split())
    cout = 0
    while x > 0 and x % d == 0:
        cout += 1
        x //= d
    if cout > 1 and (not primeCheck(x)):
        print('YES')
    elif cout > 2 and (not primeCheck(d)):
        res = False
        i = 2
        while i <= int(sqrt(d)):
            if d % i == 0:
                if x * i % d:
                    res = True
                    break
                else:
                    if x * i % d:
                        res = True
                        break
                    if x * (d // i) % d:
                        res = True
                        break
            i += 1
        if res or cout > 3:
            print('YES')
        else:
            print('NO')
    else:
        print('NO')