题目大意

给定大整数 $n$ 和其欧拉函数值 $\varphi(n)$，要求对 $n$ 进行质因数分解。

数据范围：$n < 2^{1500}$（二进制最多1500位）

算法思路

核心思想

利用已知的 $\varphi(n)$ 来辅助分解质因数。主要基于以下数学关系：

对于 $n = \prod p_i^{k_i}$，有：

$$\varphi(n) = n \prod \left(1 - \frac{1}{p_i}\right) = \prod p_i^{k_i-1}(p_i-1) $$

算法流程

1. 预处理：去除 $\varphi(n)$ 的因子 2
2. 递归分解：
   • 基础情况处理（小质数、2的幂次等）
   • 检查是否为质数的幂次
   • 利用随机化算法寻找因子

关键算法组件

1. 大整数类 bigint

• 支持二进制表示的大整数运算
• 实现加减乘除、模运算、位运算等
• 使用 unsigned long long 数组存储数据

2. Barrett 模约减

namespace Barett {
    bigint m, p;
    void init(bigint pp) {
        // 预计算用于快速模运算的参数
        len = (sz(pp.data) + 1) * 64 * 2;
        m = (bigint(1) << len) / pp;
        p = pp;
    }
    bigint mod(bigint x) {
        // 使用 Barrett 约减算法快速计算 x mod p
        bigint t = (x * m >> len) * p;
        return (x >= t) ? x - t : x - t + p;
    }
}

3. 质因数分解主算法

基础情况处理

vector<bigint> solve(bigint n) {
    if (n == 1) return {};
    if (n == 2) return {n};
    if (!(n.data[0] & 1)) {  // 偶数情况
        auto res = solve(n >> 1);
        res.insert(res.begin(), 2);
        return res;
    }
    // ... 继续处理奇数情况
}

检查质数幂次

// 检查 n 是否为某个数的 k 次幂
L(i, 2, cnt) {
    bigint l = 2, r = getPow(2, (sz(n.data) + 1) * 64 / i);
    // 二分查找底数
    while (l < r) {
        bigint mid = (l + r + 1) >> 1;
        if (getPow(mid, i) <= n) l = mid;
        else r = mid - 1;
    }
    if (getPow(l, i) == n) {
        // 找到幂次分解
        auto ans = solve(l);
        // 复制因子 i 次
        // ...
    }
}

随机化因子寻找

L(s, 1, 7) {  // 尝试7次随机算法
    bigint a = getRnd(2, n - 1);
    bigint mul = getPow(a, phi, n);  // a^phi(n) mod n
    
    // 方法1：直接检查gcd
    bigint m = getGcd(a, n);
    if (m > bigint(1)) {
        auto ans = solve(m);
        auto tmp = solve(n / m);
        ans.insert(ans.end(), tmp.begin(), tmp.end());
        return ans;
    }
    
    // 方法2：利用平方根寻找因子
    while (mul * mul % n != bigint(1)) {
        mul = mul * mul % n;
    }
    if (mul != 1) {
        m = getGcd(mul - 1, n);
        if (m > bigint(1) && m < n) {
            // 找到非平凡因子
            // ...
        }
    }
}

4. 快速幂算法

bigint getPow(bigint x, bigint y, bigint p) {
    bigint mul = bigint(1);
    while (y) {
        if (y.data[0] & 1) {
            mul = Barett::mod(mul * x);
        }
        x = Barett::mod(x * x);
        y >>= 1;
    }
    return mul;
}

5. 二进制GCD算法

bigint getGcd(bigint a, bigint b) {
    int sft = 0;
    while (a != 0) {
        if (a > b) swap(a, b);
        // 根据奇偶性进行不同的操作
        bool fa = a.data[0] & 1, fb = b.data[0] & 1;
        if (fa && fb) b -= a;
        else if (fa) b >>= 1;
        else if (fb) a >>= 1;
        else { a >>= 1; b >>= 1; sft++; }
    }
    return b << sft;
}

算法复杂度

• 时间复杂度：依赖于输入数的因子结构，最坏情况指数级，但实际表现较好
• 空间复杂度：$O(\log n)$ 存储中间结果

关键优化

1. Barrett 约减：加速模运算
2. 二进制 GCD：避免昂贵的除法操作
3. 幂次检测：提前处理质数幂次情况
4. 随机化：多次尝试提高成功率

适用场景

该算法特别适用于：

• 已知 $\varphi(n)$ 的情况
• 大整数分解（可达1500位二进制）
• 竞赛环境下的质因数分解问题

总结

本题通过结合数论知识和随机化算法，利用已知的 $\varphi(n)$ 有效分解大整数。算法包含多个优化层次，从简单情况处理到复杂的随机化因子寻找，体现了现代整数分解算法的核心思想。