PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N, find three distinct positive integers A, B, C such that the pairwise product of any two is a divisor of N, and the product of all three is a multiple of N.
EXPLANATION:
For convenience, let’s suppose 1 \leq A \lt B \lt C.
First, note that since AB, BC, AC should all be divisors of N, each of A, B, C must themselves be divisors of N.
We’d like all three to be distinct, so if N = 1 or N is prime, the answer is -1
since N doesn’t even have three distinct divisors.
Also note that C = N is impossible.
Why?
We’ll always have B \gt 1, so if C = N then BC would be strictly larger than N, and hence cannot be a divisor of it.
This further tells us that if N = p^2 for a prime p, then the answer is -1
(since p^2 doesn’t have three distinct factors smaller than it).
In every other case, finding an answer is always possible.
One simple construction is as follows: pick A = 1, B = p, C = N/p where p is some prime dividing N. It’s easy to verify that this always works when N is neither a prime nor a square of a prime.
So, we need to do the following:
- Check whether N is prime.
- Check whether N is the square of a prime.
- If N is neither, find some prime divisor of N.
This is easy to do in \mathcal{O}(\sqrt N) by slightly modifying the standard primality check algorithm: simply iterate over numbers from 2 to \sqrt{N}, and the first time you find a divisor, return it.
Ensure that the divisor you return isn’t the square root of N; and if you don’t find any such divisor, the answer is -1
.
TIME COMPLEXITY:
\mathcal{O}(\sqrt{N}) per testcase.
CODE:
Code (Python)
def findprime(n):
for i in range(2, n+1):
if i*i > n: break
if n%i == 0: return i
return -1
for _ in range(int(input())):
n = int(input())
p = findprime(n)
if n == 1 or p == -1 or p*p == n: print(-1)
else: print(1, p, n//p)