「一本通 6.3 练习 1」X-factor Chain

形式化题目

给定正整数 $x$ （ $1 \le x \le 2^{20}$ ）。构造一个满足下列条件的严格递增整数序列 $a_1, a_2, \dots, a_k$ ：

$a_1 > 1$ 且 $a_k = x$ ；
对于所有 $1 \le i < k$ ，均有 $a_i \mid a_{i+1}$ 。

求该序列的最大可能长度 $k$ ，以及达到该最大长度的不同序列的方案总数。

正解

思路

1. 最大长度与质因数分解

设 $a_0 = 1$ 。序列中的相邻两项满足整除关系，令每一步的商为 $r_i = \frac{a_i}{a_{i-1}}$ （ $1 \le i \le k$ ）。则所有商的乘积恰好等于 $x$ ：

\prod_{i=1}^k r_i = \frac{a_1}{a_0} \times \frac{a_2}{a_1} \times \dots \times \frac{a_k}{a_{k-1}} = a_k = x

由于要求每个 $a_i > a_{i-1}$ ，所以每个商 $r_i$ 都是大于 $1$ 的整数。要使链的长度 $k$ 达到最大，每一步的乘数 $r_i$ 必须尽可能小且不可再被拆分，即每一个 $r_i$ 都必须是一个质数。若存在某个 $r_i$ 为合数，设 $r_i = u \cdot v$ （ $u, v > 1$ ），则可在 $a_{i-1}$ 与 $a_i$ 之间插入 $a_{i-1} \cdot u$ ，从而使链的长度增加 $1$ 。

因此，根据算术基本定理，将 $x$ 分解质因数：

x = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m}

序列的最大可能长度

k

恰好等于所有质因子的指数之和：

k = \sum_{j=1}^m \alpha_j

2. 最大长度序列的个数

整除链的每一步相当于选择一个质因子乘上去。因此，构造一条最大长度的链，等价于将这 $k$ 个质因子（其中第 $j$ 种质因子 $p_j$ 出现 $\alpha_j$ 次）排成一个顺序 $(q_1, q_2, \dots, q_k)$ 。每一个确定的排列 $(q_1, q_2, \dots, q_k)$ 都唯一对应一条整除链：

a_1 = q_1,\quad a_2 = q_1 q_2,\quad \dots,\quad a_k = \prod_{t=1}^k q_t = x

这构成了质因子多重集的全排列计数问题。方案总数为：

\text{总方案数} = \frac{k!}{\alpha_1! \alpha_2! \dots \alpha_m!} = \frac{(\sum_{j=1}^m \alpha_j)!}{\prod_{j=1}^m (\alpha_j!)}

3. 算法实现

由于 $x \le 2^{20} = 1048576$ ，质因数分解只需试除到 $\sqrt{x} \le 1024$ 。预先筛选出 $\le 1024$ 的所有质数，对每个输入的 $x$ 进行试除分解，记录每个质因子的重数 $\alpha_j$ ，累加求出最大长度 $k$ ，并利用公式计算多重组合数即可。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
import math
from functools import reduce
from operator import mul

# 预处理素数表（由于 x <= 2^20 ≈ 1048576，质因子分解只需要试除到 sqrt(x) <= 1024）
MAX_P = 1024
IS_PRIME = [True] * (MAX_P + 1)
IS_PRIME[0] = IS_PRIME[1] = False
for i in range(2, int(MAX_P**0.5) + 1):
    if IS_PRIME[i]:
        IS_PRIME[i * i : MAX_P + 1 : i] = [False] * len(range(i * i, MAX_P + 1, i))
PRIMES = [i for i, p in enumerate(IS_PRIME) if p]


def factorize(x: int) -> list[int]:
    """分解正整数 x 的质因数，返回各质因子的出现次数列表。"""
    counts = []
    for p in PRIMES:
        if p * p > x:
            break
        if x % p == 0:
            cnt = 0
            while x % p == 0:
                cnt += 1
                x //= p
            counts.append(cnt)
    if x > 1:
        counts.append(1)
    return counts


def solve() -> None:
    lines = sys.stdin.read().split()
    if not lines:
        return
    for line in lines:
        x = int(line)
        counts = factorize(x)
        max_len = sum(counts)
        # 多重集的排列数：(sum(counts))! / (count_1! * count_2! * ... * count_k!)
        ans = math.factorial(max_len) // reduce(mul, (math.factorial(c) for c in counts), 1)
        print(f"{max_len} {ans}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:14
 * update_at: 2026-10-05 23:14
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXP = 1024; // x <= 2^20，试除到 sqrt(x) <= 1024 即可

int primes[200]; // 预处理得到的 <= 1024 的素数
int prime_cnt;   // 素数个数

ll fact[64]; // fact[i] = i!，x <= 2^20 时质因子总个数 k <= 20

// 埃氏筛预处理 <= MAXP 的素数，供试除分解质因数使用。
void init_primes() {
    bool is_prime[MAXP + 1];
    for (int i = 0; i <= MAXP; i++) is_prime[i] = true;
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i * i <= MAXP; i++) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= MAXP; j += i) is_prime[j] = false;
    }
    prime_cnt = 0;
    for (int i = 2; i <= MAXP; i++) {
        if (is_prime[i]) primes[prime_cnt++] = i;
    }
}

// 预处理阶乘，用于计算多重集排列数。
void init_fact() {
    fact[0] = 1;
    for (int i = 1; i < 64; i++) fact[i] = fact[i - 1] * i;
}

// 对单个 x 求答案：最大链长 = 质因子指数之和 k，方案数 = k! / (各指数阶乘之积)。
void solve_one(ll x) {
    ll total = 0; // 质因子指数之和，即最大链长 k
    ll denom = 1; // 分母：各质因子指数阶乘的乘积
    ll rest = x;
    for (int i = 0; i < prime_cnt; i++) {
        ll p = primes[i];
        if (p * p > rest) break;
        if (rest % p == 0) {
            ll cnt = 0;
            while (rest % p == 0) {
                rest /= p;
                cnt++;
            }
            total += cnt;
            denom *= fact[cnt];
        }
    }
    if (rest > 1) total += 1; // 剩下一个大于 1 的质因子
    cout << total << " " << fact[total] / denom << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init_primes();
    init_fact();

    ll x;
    while (cin >> x) { // 多组数据读到文件结束
        solve_one(x);
    }

    return 0;
}

复杂度

时间复杂度：
- 预处理：筛选 $\le 1024$ 的素数，耗时可忽略不计。
- 单次查询：试除最多 172 个素数，时间复杂度为 $O(\frac{\sqrt{x}}{\ln \sqrt{x}})$ ；阶乘及除法计算仅需 $O(k)$ （其中 $k \le 20$ ）。
- 总时间复杂度为 $O(\pi(\sqrt{x_{\max}}) + T \cdot \pi(\sqrt{x}))$ ，在时限内非常充裕。
空间复杂度：只需存储 $1024$ 以内的素数表，空间复杂度为 $O(\sqrt{x_{\max}})$ 。

总结

本题的关键在于通过商的拆分建立起整除链与算术基本定理的联系：

链长极大化 $\iff$ 链的每一步乘数不可约（均为质数），链长即为质因子重数之和；
序列计数 $\iff$ 质因子多重集的全排列。

图示解析

以样例中 $x = 100$ 为例： $100 = 2^2 \times 5^2$ ，质因子为重集 $\{2, 2, 5, 5\}$ 。

最大长度 $k = 2 + 2 = 4$ ；
方案数为 $\frac{4!}{2! \times 2!} = 6$ 种。

下表展示了质因子的 6 种不同排列与生成的因子链的对应关系：

排列 $(q_1, q_2, q_3, q_4)$	对应的整除链 $a_1 \to a_2 \to a_3 \to a_4$
$2, 2, 5, 5$	$2 \to 4 \to 20 \to 100$
$2, 5, 2, 5$	$2 \to 10 \to 20 \to 100$
$2, 5, 5, 2$	$2 \to 10 \to 50 \to 100$
$5, 2, 2, 5$	$5 \to 10 \to 20 \to 100$
$5, 2, 5, 2$	$5 \to 10 \to 50 \to 100$
$5, 5, 2, 2$	$5 \to 25 \to 50 \to 100$