首页 程序设计 小学数学

# 唯一分解定理

唯一分解定理断言：任何一个大于 11 的整数 nn 都可以分解成若干个素因数的乘积，如果不记各素因数的顺序，那么这种分解是唯一的

n=p1a1⋅p2a2⋅⋅⋅pkakn=p_1^{a_1}·p_2^{a_2}···p_k^{a_k}

其中，pip_i 是素数，aia_i 为正整数

# 例题 - 阶层约数

# 题目大意

求 100!100! 的约数个数

# 题解

对于 100!100! 有， 100! = 1 * 2 * ... * 99 * 100
先把 100100 以内的所有素数预处理出来，然后对于 11 到 100100 进行唯一分解，可以得到

100=p1a1⋅p2a2⋅⋅⋅pkak100 = p_1^{a_1}·p_2^{a_2}···p_k^{a_k}

显然，约数个数为 ∏i=1k(ai+1)\prod_{i=1}^{k} {(a_i + 1)}

C++
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
bool noPrime[N];
vector<int> prime;

void init(int n) {
    noPrime[1] = 1;
    for (int i = 1; i <= n; i++) {
        if (!noPrime[i])
            prime.push_back(i);
        for (int p : prime) {
            if (p * i > n)
                break;
            noPrime[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

void solve () {
    int res = 1;
    init(100);
    vector<int> cnt(prime.size(), 0);
    cout << 1 << endl;
    for (int i = 1; i <= 100; i++) {
        int t = i;

        for (int j = 0; j < prime.size() && prime[j] <= t && t != 1; j++)
            while (t % j == 0 && t != 1)
                t /= j, cnt[j]++;
    }

    for (int i = 0; i < cnt.size(); i++)
        res *= (cnt[i] + 1);

    cout << res << endl;
}