分解因数

题目描述

给出正整数 $a>1$ ，把它分解成若干个正整数的乘积 $a=a_1\times a_2\times\cdots\times a_n$ ，要求 $1<a_1\leqslant a_2\leqslant\cdots\leqslant a_n$ ，问有多少种分解， $a=a$ 也算一种。输入第一行是数据组数 $n$ ，随后 $n$ 行每行一个 $a$ （ $1<a<32768$ ）；对每组数据输出一行分解种数。样例输入 2 / 2 / 20 对应输出 1 / 4。

思路

设 $f(n,lo)$ 为把 $n$ 拆成若干不小于 $lo$ 的因子之积的方案数，因子非降序写成 $lo\le d\le n/d$ ，即首因子只需枚举到 $\lfloor\sqrt n\rfloor$ 且 $d\mid n$ ，于是 $f(n,lo)=1+\sum_{d}f(n/d,d)$ 。初值 $1$ 对应"不再往下拆"即 $n$ 本身这一种分解，把下界从 $lo$ 收紧成 $d$ 保证每个无序分解只被数一次，答案是 $f(a,2)$ 。同一状态被不同分支反复用到，记忆化后即可。

参考代码

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#!/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-09-29 23:20
# update_at: 2026-09-29 23:20

import sys
from functools import cache
from math import isqrt

MIN_FACTOR = 2  # 题面要求每个因子 a_i 都大于 1；它同时是"选取下一个因子的下界"初值


@cache
def count(n: int, lo: int) -> int:
    """把 n 拆成若干个 >= lo 的因子之积（无序、因子可重复）的方案数。

    `lo` 是当前这一位因子的下界：上一轮选了 d，剩下 n/d 的下界就是 d，
    保证因子序列非降序，从而每个无序分解只被数一次。
    结果含"单因子 n 本身"这一种分解，所以初值取 1。
    """
    # 只枚举不超过 sqrt(n) 的首因子：再大的首因子会强迫第二位小于自己，违反非降序
    return 1 + sum(count(n // d, d) for d in range(lo, isqrt(n) + 1) if n % d == 0)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)

    # 递归只在 n % d == 0 且 d <= isqrt(n) 时发生，于是 n//d >= d，调用点恒有 n >= lo；
    # 题面又保证 a > 1，所以永远不会走到 n < lo 这种会多算 1 的边界。
    out = [count(next(data), MIN_FACTOR) for _ in range(T)]
    print('\n'.join(map(str, out)))


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/**
 * 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 05:19
 * update_at: 2026-10-05 05:19
 */

#include <cstdio>

const int MAXA = 32768; // a 的取值范围上界（题面：1 < a < 32768）
const int MAXLO = 182;  // 因子下界 lo 不超过 sqrt(32767) = 181，留一点余量

typedef long long ll;

// memo[n][lo] = 把 n 拆成若干个不小于 lo 的因子之积的方案数；0 表示还没算过。
// 答案最大只有 1713（a = 30240 时），用 int 足够，可省一半内存。
int memo[MAXA][MAXLO];

// 求把 n 拆成若干不小于 lo 的因子之积（因子非降序、可重复）的方案数。
// 非降序写法让每个无序分解只被数一次，因此不需要 set 去重。
int count_ways(int n, int lo) {
    if (memo[n][lo] != 0) return memo[n][lo]; // 记忆化：同一状态只算一次
    int res = 1; // 初值 1 表示不再往下拆，正好对应题面的 a = a 这一种分解
    // 非降序要求首因子 d 满足 d <= n/d，即 d*d <= n；d <= 181，int 乘法不会溢出
    for (int d = lo; d * d <= n; ++d) {
        if (n % d == 0) res += count_ways(n / d, d); // 选 d 后，剩下 n/d 的因子下界收紧到 d
    }
    memo[n][lo] = res;
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        int a;
        scanf("%d", &a);
        printf("%d\n", count_ways(a, 2)); // 合法因子最小是 2
    }
    return 0;
}

目录

题目描述

思路

参考代码