质因数分解

vector<pair<long long, int>> prime_factor(long long x) {
    vector<pair<long long, int>> res;
    for (int i = 2 ; 1LL * i * i <= x ; i++) {
        if (x % i == 0) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            res.emplace_back(i, cnt);
        }
    }
    if (x > 1) {
        res.emplace_back(x, 1);
    }
    return res;
}

namespace Miller_Rabin {
    using i64 = long long;
    i64 qpow(__int128 a, i64 b, i64 P) {
        __int128 res = 1;
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }
    bool Miller_Rabin(i64 n, const vector<i64> &as) {
        i64 d = n - 1;
        while (d % 2 == 0) {
            d /= 2;
        }
        i64 e = 1, rev = n - 1;
        for (auto &a : as) {
            if (n <= a) {
                break;
            }
            i64 t = d;
            __int128 y = qpow(a, t, n);
            while (t != n - 1 && y != e && y != rev) {
                y = y * y % n;
                t *= 2;
            }
            if (y != rev && t % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    bool is_prime(i64 n) {
        if (n % 2 == 0) {
            return n == 2;
        }
        if (n <= 1) {
            return false;
        }
        if (n < (1LL << 30)) {
            return Miller_Rabin(n, {2, 7, 61});
        }
        return Miller_Rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    }
} // Miller_Rabin
using Miller_Rabin::is_prime; // 判断是否是质数
namespace Pollard_rho {
    template<class T>
    struct Random {
        mt19937 mt;
        Random() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
        T operator()(T L, T R) {
            uniform_int_distribution<int64_t> dist(L, R);
            return dist(mt);
        }
    };
    Random<i64> rng;
    i64 get(i64 n) {
        if (n % 2 == 0) {
            return 2;
        }
        if (is_prime(n)) {
            return n;
        }
        i64 R;
        auto f = [&](__int128 x) {
            return (x * x + R) % n;
        };
        while (true) {
            i64 x, y, ys, q = 1;
            R = rng(2, n - 1), y = rng(2, n - 1);
            i64 g = 1;
            int m = 128;
            for (int r = 1 ; g == 1 ; r *= 2) {
                x = y;
                for (int i = 0 ; i < r ; i++) {
                    y = f(y);
                }
                for (int k = 0 ; g == 1 && k < r ; k += m) {
                    ys = y;
                    for (int i = 0 ; i < m && i < r - k ; i++) {
                        y = f(y);
                        q = (__int128) q * (((x - y) % n + n) % n) % n;
                    }
                    g = __gcd(q, n);
                }
            }
            if (g == n) {
                do {
                    ys = f(ys);
                    g = __gcd(((x - ys) % n + n) % n, n);
                } while (g == 1);
            }
            if (g != n) {
                return g;
            }
        }
        return 0;
    }
    vector<i64> factorize(i64 n) {
        if (n <= 1) {
            return {};
        }
        i64 p = get(n);
        if (p == n) {
            return {n};
        }
        auto L = factorize(p);
        auto R = factorize(n / p);
        copy(R.begin(), R.end(), back_inserter(L));
        return L;
    }
    vector<pair<i64, int>> prime_factor(i64 n) {
        auto ps = factorize(n);
        sort(ps.begin(), ps.end());
        vector<pair<i64, int>> res;
        for (auto &e : ps) {
            if (!res.empty() && res.back().first == e) {
                res.back().second++;
            } else {
                res.emplace_back(e, 1);
            }
        }
        return res;
    }
    vector<i64> divisors(i64 n) {
        auto ps = prime_factor(n);
        int cnt = 1;
        for (auto &[p, t] : ps) {
            cnt *= t + 1;
        }
        vector<i64> res(cnt, 1);
        cnt = 1;
        for (auto &[p, t] : ps) {
            i64 pw = 1;
            for (int i = 1 ; i <= t ; i++) {
                pw *= p;
                for (int j = 0 ; j < cnt ; j++) {
                    res[cnt * i + j] = res[j] * pw;
                }
            }
            cnt *= t + 1;
        }
        return res;
    }
} // Pollard_rho
using Miller_Rabin::is_prime; // 判断质数
using Pollard_rho::prime_factor; // 所有质因子 (质因子, 个数)
using Pollard_rho::divisors; // 所有因子