O(n^{1/3}) 确定性分解质因数

Whitely · 2026-02-13 23:43:10 · 算法·理论

Dirichlet 逼近定理: 任意 n>1(n\in \mathbb R) 和比例 \alpha，存在 \frac{p}{q}(1\le q\le n) 使 |\alpha-\frac{p}{q}|<\frac{1}{nq}。

整个做法由上述定理启发。同时我印象中有类似复杂度的做法但未在网上找到。

处理掉 \le n^{1/3} 的因数，此时 n 至多两个质因子，假设存在 pq=n(n^{1/3}<p\le q<n^{2/3})。

用 \frac{u}{v} 逼近 \frac{q}{p}，由上述定理，存在 1\le v\le pn^{-1/3} 满足 |up-vq|<n^{1/3}。

进一步地，由这两个范围可以得出 uv\le n^{1/3}，下设 x=up+vq,y=|up-vq|,z=uv。

若能解出 (y,z) 即可得出 x，特判掉 n 很小的情况，有 1<\gcd(x-y,n)<n 为 p,q 之一。

其满足 x^2-y^2=4zn，利用 0\le y\le n^{1/3} 分析 x 的范围，有 0\le x-2\sqrt{zn}=\frac{y^2}{x+2\sqrt {zn}}\le \frac{n^{2/3}}{4\sqrt{zn}}=\frac{n^{1/6}}{4\sqrt z}，故 (z,x) 组数为 \frac{n^{1/6}}{4}\sum_{z=1}^{n^{1/3}}\frac{1}{\sqrt z}=\mathcal O(n^{1/3})。

这样 \mathcal O(n^{1/3}) 跑满，以下是洛谷 P4718 TLE95 参考代码。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline bool isqr(ll n, ll &rt) { return n < 0 ? 0 : (rt = sqrtl(n)) * rt == n; }
ll p3, _p6, _, m, res;
ll d(ll n) {
  p3 = pow(n, 1.0 / 3), _p6 = pow(n, 1.0 / 6) / 4;
  __int128 t = 4 * n;
  for (ll k = 1; k <= p3; ++k, t += 4 * n)
    for (ll x = sqrtl(t) + 0.5, y, xr = x + _p6 / sqrtl(k) + 1; x <= xr; ++x) if (isqr((__int128)x * x - t, y)) return __gcd(x - y, n);
  return 1;
}
signed main() {
  cin >> _;
  while (_--) {
    ll n; cin >> n, m = n, res = 0, p3 = pow(n, 1.0 / 3);
    for (int i = 2; i <= p3; ++i) while (n % i == 0) n /= i, res = i;
    ll t = d(n); ((res = max(res, max(t, n / t))) == m) ? cout << "Prime\n" : cout << res << '\n';
  }
  return 0;
}