D - Happy New Year 2023 Editorial by en_translator
A famous algorithm to factorize a given integer \(N\) is an \(O(\sqrt{N})\)-algorithm that checks if \(N\) is divisible by \(i\) for each \(i=1,2,\dots,\lfloor\sqrt{N}\rfloor\) (so-called “trial division”).
Why up to \(\lfloor\sqrt{N}\rfloor\) is enough?
Let \(N'\) be the number resulting from dividing \(N\) by all prime factors up to \(\lfloor\sqrt{N}\rfloor\). If \(N'=1\), we have already found all the prime factors, so we assume \(N' > 1\). Here, since the minimum possible prime factor of \(N'\) is \(\lfloor\sqrt{N}\rfloor+1\), whose square exceeds \(N\) (the assumption that \(N'\) has two or more prime factors contradicts with the obvious inequality \({N'} \leq N\)), \(N'\) turns out to be a prime. The prime factorization is complete, including the factors found in the initial trial division.
However, the \(N\) in this problem is too large for \(O(\sqrt{N})\) trial division. Here we use the representation \(N=p^2q\) (where \(p\) and \(q\) are primes).
An important fact is that \(\min(p,q)\leq\sqrt[3]{N}\) (otherwise, we have \(p^2q>N\), which is a contradiction). Thus, we can find at least one of \(p\) and \(q\) by doing trial division up to \(\sqrt[3]{N}\). The idea motivates the following specific algorithm:
- Let \(A\) be the maximum integer \(i\) among \(i=1,2,\dots,\lfloor\sqrt[3]{N}\rfloor\) that divides \(N\) (actually, \(A=p\) or \(A=q\)).
- Check if \(\frac{N}{A}\) divides \(A\). If it is divisible, \(p=A\) and \(q = \frac{N}{A^2}\); otherwise, \(p = \sqrt{\frac{N}{A}}\) and \(q=A\).
Therefore, the problem has been solved in an \(O(\sqrt[3]{N})\) time per test case.
Note that one can solve this problem with a fast prime factorization algorithm like Pollard’s rho algorithm.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
ll p = 0, q = 0;
for (ll i = 2; i * i * i <= n; i++) {
if (n % i != 0) continue;
if ((n / i) % i == 0) {
p = i;
q = n / i / i;
} else {
q = i;
p = (ll) round(sqrt(n / i));
}
break;
}
cout << p << ' ' << q << endl;
}
}
posted:
last update: