Division (Codeforces 1444A)
Tags: Math, number theory

Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.To improve his division skills, Oleg came up with $$$t$$$ pairs of integers $$$p_i$$$ and $$$q_i$$$ and for each pair decided to find the greatest integer $$$x_i$$$, such that:   $$$p_i$$$ is divisible by $$$x_i$$$;  $$$x_i$$$ is not divisible by $$$q_i$$$.  Oleg is really good at division and managed to find all the answers quickly, how about you?

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of pairs.Each of the following $$$t$$$ lines contains two integers $$$p_i$$$ and $$$q_i$$$ ($$$1 \le p_i \le 10^{18}$$$; $$$2 \le q_i \le 10^{9}$$$) — the $$$i$$$-th pair of integers.

Output: Print $$$t$$$ integers: the $$$i$$$-th integer is the largest $$$x_i$$$ such that $$$p_i$$$ is divisible by $$$x_i$$$, but $$$x_i$$$ is not divisible by $$$q_i$$$.One can show that there is always at least one value of $$$x_i$$$ satisfying the divisibility conditions for the given constraints.

Note: For the first pair, where $$$p_1 = 10$$$ and $$$q_1 = 4$$$, the answer is $$$x_1 = 10$$$, since it is the greatest divisor of $$$10$$$ and $$$10$$$ is not divisible by $$$4$$$.For the second pair, where $$$p_2 = 12$$$ and $$$q_2 = 6$$$, note that   $$$12$$$ is not a valid $$$x_2$$$, since $$$12$$$ is divisible by $$$q_2 = 6$$$;  $$$6$$$ is not valid $$$x_2$$$ as well: $$$6$$$ is also divisible by $$$q_2 = 6$$$.  The next available divisor of $$$p_2 = 12$$$ is $$$4$$$, which is the answer, since $$$4$$$ is not divisible by $$$6$$$.

Sample Inputs:
3
10 4
12 6
179 822

Sample Outputs:
10
4
179

Solution (Python):
def find_prime(n):
    ans = []
    i = 2
    x = n
    while i * i <= n:
        if x % i == 0:
            ans.append(i)
            while x % i == 0:
                x //= i
        i += 1
    if x > 1:
        ans.append(x)
    return ans
for _ in range(int(input())):
    (p, a) = map(int, input().split())
    if p % a != 0:
        print(p)
    else:
        mul = find_prime(a)
        ans = 1
        for i in mul:
            t = p
            while t % a == 0:
                t //= i
            ans = max(ans, t)
        print(ans)

Solution (Python):
from math import isqrt
for _ in range(int(input())):
    (a, b) = [int(i) for i in input().split()]
    if b > a:
        print(a)
        continue
    if a % b:
        print(a)
        continue
    (d, p, aa) = ({}, isqrt(b), a)
    for i in range(2, p + 1):
        if b % i == 0:
            d[i] = 0
            while b % i == 0:
                d[i] += 1
                b //= i
    if b > 1:
        d[b] = 1
    r = float('inf')
    for e in d:
        c = 0
        while a % e == 0:
            c += 1
            a //= e
        r = min(r, e ** (c - (d[e] - 1)))
    print(aa // r)

Solution (Python):
for _ in range(int(input())):
    (p, q) = map(int, input().split())
    pd = []
    q2 = q
    for i in range(2, int(q2 ** 0.5) + 2):
        if q2 % i == 0:
            while q2 % i == 0:
                q2 //= i
            pd.append(i)
    if q2 != 1:
        pd.append(q2)
    ans = 1
    for a in pd:
        z = p
        while z % a == 0:
            z //= a
        while p % (z * a) == 0 and z * a % q != 0:
            z *= a
        ans = max(ans, z)
    print(ans)