Two Divisors (Codeforces 1366D)
Tags: Math, number theory

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.For each $$$a_i$$$ find its two divisors $$$d_1 > 1$$$ and $$$d_2 > 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ (where $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$) or say that there is no such pair.

Input: The first line contains single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the size of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) — the array $$$a$$$.

Output: To speed up the output, print two lines with $$$n$$$ integers in each line.The $$$i$$$-th integers in the first and second lines should be corresponding divisors $$$d_1 > 1$$$ and $$$d_2 > 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ or $$$-1$$$ and $$$-1$$$ if there is no such pair. If there are multiple answers, print any of them.

Note: Let's look at $$$a_7 = 8$$$. It has $$$3$$$ divisors greater than $$$1$$$: $$$2$$$, $$$4$$$, $$$8$$$. As you can see, the sum of any pair of divisors is divisible by $$$2$$$ as well as $$$a_7$$$.There are other valid pairs of $$$d_1$$$ and $$$d_2$$$ for $$$a_{10}=24$$$, like $$$(3, 4)$$$ or $$$(8, 3)$$$. You can print any of them.

Sample Inputs:
10
2 3 4 5 6 7 8 9 10 24

Sample Outputs:
-1 -1 -1 -1 3 -1 -1 -1 2 2 
-1 -1 -1 -1 2 -1 -1 -1 5 3

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
bd = 10 ** 7 + 1
ar = list(range(bd + 1))
for i in range(2, int(bd ** (1 / 2)) + 1):
    if ar[i] == i:
        for j in range(i * i, bd + 1, i):
            ar[j] = i
n = int(input())
a = list(map(int, input().split()))
ans1 = []
ans2 = []
for i in a:
    x = i
    z = ar[x]
    while x % z == 0:
        x //= z
    if x == 1:
        ans1.append(-1)
        ans2.append(-1)
    else:
        ans1.append(z)
        ans2.append(x)
print(*ans1)
print(*ans2)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())

def comb(n, m):
    return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
    return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial, ceil, sqrt
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
    up = 10 ** 7
    pri = [-1] * (up + 1)
    for i in range(2, ceil(sqrt(up)) + 1):
        if pri[i] == -1:
            for j in range(i, up + 1, i):
                pri[j] = i
    n = N()
    arr = RLL()
    (resa, resb) = ([], [])
    for i in arr:
        if pri[i] == -1:
            resa.append(-1)
            resb.append(-1)
        else:
            d1 = pri[i]
            d2 = i
            while d2 % d1 == 0:
                d2 //= d1
            if d2 == 1:
                resa.append(-1)
                resb.append(-1)
            else:
                resa.append(d1)
                resb.append(d2)
    print(*resa)
    print(*resb)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split(' ')))

def get_int_grid(n):
    return [get_ints() for _ in range(n)]

def get_str():
    return input().strip()

def get_strs():
    return get_str().split(' ')

def flat_list(arr):
    return [item for subarr in arr for item in subarr]

def yes_no(b):
    if b:
        return 'YES'
    else:
        return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
    """"""
    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p

def solve_d():
    n = get_int()
    a = get_ints()

    def linear_sieve(n):
        primes = []
        lpd = [0] * (n + 1)
        for i in range(2, n + 1):
            if lpd[i] == 0:
                lpd[i] = i
                primes.append(i)
            for p in primes:
                if i * p > n or p > lpd[i]:
                    break
                lpd[i * p] = p
        return (primes, lpd)
    (primes, lpd) = linear_sieve(max(a))
    d1 = []
    d2 = []

    def get(z):
        y = z
        d = lpd[y]
        while y % d == 0:
            y //= d
        if y > 1:
            return (y, z // y)
        else:
            return (-1, -1)
    d1 = []
    d2 = []
    for x in a:
        (u, v) = get(x)
        d1.append(u)
        d2.append(v)
    return (d1, d2)
ans = solve_d()
for item in ans:
    print(*item)