Official

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:

  1. 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\)).
  2. 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: