// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// IntFactorization.hpp
// 完全素因数分解ディスパッチャ
// 移植元: lib++20 整数.素因数分解.cpp (_Factor, 素因数分解)

#pragma once

#include "IntBase.hpp"
#include "IntPrime.hpp"
#include "IntGCD.hpp"
#include "IntModular.hpp"

#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <sstream>

namespace calx {

/**
 * @brief 完全素因数分解ディスパッチャ
 *
 * 複数の因数探索アルゴリズムを組み合わせて完全な素因数分解を行います。
 *
 * 戦略:
 *   1. 小素数バッチ GCD で 2〜1987 の因数を除去
 *   2. 残余に対して因数探索を段階的に適用:
 *      - Pollard p-1 (p-1 が smooth な因数に有効)
 *      - Pollard rho / Brent (汎用、O(n^{1/4}))
 *      - Fermat 法 (近い因数のペアに有効)
 *   3. 合成数の因数を再帰的に分解
 *   4. 結果を素因数の昇順でソート
 */
class IntFactorization {
public:
    /**
     * @brief 完全素因数分解
     *
     * n を素因数の積に完全に分解します。
     *
     * @param n 分解する整数 (n > 1)
     * @param millerRabinK Miller-Rabin テストの回数（デフォルト 20）
     * @return 素因数と指数のペアのベクトル {{p1,e1}, {p2,e2}, ...}
     *         p1 < p2 < ... の昇順
     *
     * 特殊ケース:
     *   factorize(0) → {{0, 1}}
     *   factorize(1) → {}
     *   factorize(-n) → factorize(n) (符号は無視)
     *   factorize(素数) → {{p, 1}}
     *
     * 例:
     *   factorize(360) → {{2,3}, {3,2}, {5,1}}
     *   factorize(2^32-1) → {{3,1}, {5,1}, {17,1}, {257,1}, {65537,1}}
     */
    static std::vector<std::pair<Int, int>> factorize(const Int& n, int millerRabinK = 20);

    /**
     * @brief 単一因数探索（非自明な因数を1つ見つける）
     *
     * 複数のアルゴリズムを段階的に試し、n の非自明な因数を1つ返します。
     *
     * @param n 合成数 (n > 1)
     * @param millerRabinK Miller-Rabin テストの回数
     * @return n の非自明な因数。見つからなければ n を返す
     */
    static Int findFactor(const Int& n, int millerRabinK = 20);

    /**
     * @brief 素因数分解結果を文字列で表示
     *
     * @param factors factorize() の戻り値
     * @return "2^3 * 3^2 * 5" のような文字列
     */
    static std::string toString(const std::vector<std::pair<Int, int>>& factors);
};

} // namespace calx