math/prime_factorize.hpp

• View this file on GitHub
• Last update: 2025-06-04 11:53:52+09:00
• Include: #include "math/prime_factorize.hpp"

Depends on

• math/is_prime.hpp
• math_mod/pow_mod.hpp
• modint/mont_arb.hpp
• random/gen.hpp
• random/seed.hpp
• type_traits/integral.hpp
• type_traits/io.hpp

Required by

• math/group/rolling_hash.hpp
• math/multiplicative_function/euler_phi.hpp
• math/multiplicative_function/mobius.hpp
• math/multiplicative_function/sigma.hpp
• math_mod/primitive_root_64bit.hpp
• random/hash.hpp
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)
• 文字の変更が行われない文字列に対する静的なローリングハッシュ (string/static_rolling_hash.hpp)

Verified with

• verify/aoj/aoj_alds1_14_b.test.cpp
• verify/aoj/aoj_ntl_1_d.test.cpp
• verify/unit_test/famous_function_table.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/monoid.test.cpp
• verify/unit_test/prime_factorize_table.test.cpp
• verify/yosupo_math/factrize.test.cpp
• verify/yosupo_math/primitive_root.test.cpp
• verify/yosupo_string/string_z_roliha.test.cpp

Code

#ifndef KK2_MATH_PRIME_FACTORIZE_HPP
#define KK2_MATH_PRIME_FACTORIZE_HPP 1

#include <algorithm>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

#include "../math_mod/pow_mod.hpp"
#include "../modint/mont_arb.hpp"
#include "../random/gen.hpp"
#include "is_prime.hpp"

namespace kk2 {

namespace number_theory {

using i64 = long long;
using u64 = unsigned long long;

template <class mint, class T> T pollard_rho(T n) {
    if (~n & 1) return 2;
    if (is_prime(n)) return n;
    if (mint::getmod() != n) mint::setmod(n);

    mint R, one = 1;
    auto f = [&](mint x) {
        return x * x + R;
    };
    auto _rng = [&]() {
        return kk2::random::rng(2, n);
    };
    while (true) {
        mint x, y, ys, q = one;
        R = _rng(), y = _rng();
        T g = 1;
        constexpr int m = 128;
        for (int r = 1; g == 1; r <<= 1) {
            x = y;
            for (int i = 0; i < r; i++) y = f(y);
            for (int k = 0; k < r && g == 1; k += m) {
                ys = y;
                for (int i = 0; i < std::min(m, r - k); i++) {
                    y = f(y);
                    q *= x - y;
                }
                g = std::gcd(q.val(), n);
            }
        }
        if (g == n) do {
                ys = f(ys);
                g = std::gcd((x - ys).val(), n);
            } while (g == 1);
        if (g != n) return g;
    }
    exit(1);
}

std::vector<i64> inner_factorize(i64 n) {
    using mint32 = ArbitraryLazyMontgomeryModInt<54355165>;
    using mint64 = ArbitraryLazyMontgomeryModInt64bit<54355165>;
    assert(n);
    if (n < 0) n = -n;
    if (n == 1) return {};
    u64 p;
    if (n <= (1ll << 30)) {
        p = pollard_rho<mint32, unsigned int>(n);
    } else if (n <= (1ll << 62)) {
        p = pollard_rho<mint64, unsigned long long>(n);
    } else {
        exit(1);
    }
    if (i64(p) == n) return {i64(p)};
    auto l = inner_factorize(p);
    auto r = inner_factorize(n / p);
    std::copy(r.begin(), r.end(), std::back_inserter(l));
    return l;
}

std::vector<std::pair<i64, int>> factorize(i64 n) {
    auto tmp = inner_factorize(n);
    std::sort(tmp.begin(), tmp.end());
    std::vector<std::pair<i64, int>> res;
    for (int i = 0; i < (int)tmp.size(); i++) {
        if (i == 0 or res.back().first != tmp[i]) {
            res.emplace_back(tmp[i], 1);
        } else {
            res.back().second++;
        }
    }
    return res;
}

std::map<i64, int> factorize_map(i64 n) {
    auto tmp = inner_factorize(n);
    std::map<i64, int> res;
    for (auto x : tmp) res[x]++;
    return res;
}

std::vector<i64> divisors(i64 n) {
    if (n == 0) return {};

    auto f = factorize(n);
    std::vector<i64> res = {1};
    for (auto [p, k] : f) {
        int sz = res.size();
        i64 x = 1;
        for (int i = 0; i < k; i++) {
            x *= p;
            for (int j = 0; j < sz; j++) { res.emplace_back(res[j] * x); }
        }
    }
    std::sort(res.begin(), res.end());
    return res;
}

} // namespace number_theory

using number_theory::divisors;
using number_theory::factorize;
using number_theory::factorize_map;

} // namespace kk2


#endif // KK2_MATH_PRIME_FACTORIZE_HPP

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: type_traits/integral.hpp: line 4: #pragma once found in a non-first line

Back to top page