test/math/pollardrho.test.cpp

• View this file on GitHub
• Last update: 2025-11-13 05:48:47+08:00
• Problem: https://judge.yosupo.jp/problem/factorize

Depends on

• src/math/millerrabin.hpp
• src/math/pollardrho.hpp
• src/math/pow_mod_ll.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/factorize
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;

#include "../../src/math/pollardrho.hpp"

void solve() {
  ll n;
  cin >> n;
  auto factors = breakdown(n);
  cout << factors.size();
  for (ll f : factors) {
    cout << " " << f;
  }
  cout << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

#line 1 "test/math/pollardrho.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/factorize
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;

#line 1 "src/math/pollardrho.hpp"
// 时间复杂度: 期望 $\mathcal{O}(n^{1/4})$
#line 1 "src/math/millerrabin.hpp"
// 时间复杂度: $\mathcal{O}(k \log n)$，目前 $k = 9$ 足以判定 $64$ 位整数.
#line 1 "src/math/pow_mod_ll.hpp"
ll pow_mod_ll(ll a, ull n, ll p) {
  ll ret = 1;
  for (; n; n /= 2) {
    if (n & 1) ret = i128(ret) * a % p;
    a = i128(a) * a % p;
  }
  return ret;
}
#line 3 "src/math/millerrabin.hpp"
bool isprime(ll n) {
  if (n < 2) return 0;
  int s = __builtin_ctzll(n - 1);
  ll d = (n - 1) >> s;
  for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
    if (a == n) return 1;
    ll x = pow_mod_ll(a, d, n);
    if (x == 1 || x == n - 1) continue;
    bool ok = 0;
    for (int i = 0; i + 1 < s; i++) {
      x = i128(x) * x % n;
      if (x == n - 1) {
        ok = 1;
        break;
      }
    }
    if (!ok) return 0;
  }
  return 1;
}
#line 3 "src/math/pollardrho.hpp"
ll pollard_single(ll n) {
  if (n % 2 == 0) return 2;
  if (isprime(n)) return n;
  ll st = 0;
  auto f = [&](ll x) -> ll { return (i128(x) * x % n + st) % n; };
  while (true) {
    st++;
    ll x = st, y = f(x);
    while (true) {
      ll p = gcd(y - x + n, n);
      if (p == 0 || p == n) break;
      if (p != 1) return p;
      x = f(x), y = f(f(y));
    }
  }
}
vector<ll> breakdown(ll n) {
  if (n == 1) return {};
  ll x = pollard_single(n);
  if (x == n) return {n};
  auto l = breakdown(x), r = breakdown(n / x);
  l.insert(l.end(), ALL(r)), sort(ALL(l));
  return l;
}
#line 11 "test/math/pollardrho.test.cpp"

void solve() {
  ll n;
  cin >> n;
  auto factors = breakdown(n);
  cout << factors.size();
  for (ll f : factors) {
    cout << " " << f;
  }
  cout << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	4295098369_00	AC	13 ms	4 MB
g++	999381247093216751_00	AC	1903 ms	4 MB
g++	big2_00	AC	500 ms	4 MB
g++	big2_01	AC	503 ms	4 MB
g++	big2_02	AC	522 ms	4 MB
g++	big2_worse_00	AC	1217 ms	4 MB
g++	big_semiprime_gen_00	AC	489 ms	4 MB
g++	big_semiprime_gen_01	AC	485 ms	4 MB
g++	big_semiprime_random_00	AC	389 ms	4 MB
g++	big_semiprime_random_01	AC	424 ms	4 MB
g++	carmichael_00	AC	36 ms	4 MB
g++	example_00	AC	5 ms	4 MB
g++	fixed_RNG_buster_00	AC	5 ms	4 MB
g++	hack00_00	AC	5 ms	4 MB
g++	max_00	AC	31 ms	4 MB
g++	pow2_00	AC	38 ms	4 MB
g++	pow2_01	AC	39 ms	4 MB
g++	pow2_02	AC	70 ms	4 MB
g++	prime_test_special_00	AC	8 ms	4 MB
g++	prime_test_special_01	AC	13 ms	4 MB
g++	prime_test_special_02	AC	22 ms	4 MB
g++	prime_test_special_03	AC	7 ms	4 MB
g++	prime_test_special_bug_00	AC	5 ms	4 MB
g++	prime_test_special_bug_01	AC	5 ms	4 MB
g++	prime_test_special_bug_02	AC	5 ms	4 MB
g++	random_00	AC	9 ms	4 MB
g++	random_01	AC	11 ms	4 MB
g++	random_02	AC	14 ms	4 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	5 ms	4 MB

Back to top page