---
title: "阶乘分解"
created: 2025-11-28
tags:
  - 算法
---

# 阶乘分解

## 题目 [阶乘分解](https://www.acwing.com/problem/content/199/)

![[image-a5fb09cf.png]]

## 思路分析

暴力 先算阶乘 再算质因数分解

阶乘用dfs或者dp写

```cpp
#include<bits/stdc++.h>
using namespace std;

int dfs(int n){
    if(n==1)
        return 1;
    return n*dfs(n-1);
}

const int N=1e6+10;
int f[N];

int main()
{
    int n;
    cin>>n;
    // int x=dfs(n);

    f[n]=n;
    for(int i=n-1;i>=1;i--)
        f[i]=i*f[i+1];
    // cout<<f[1];

    int x=f[1];
    for(int i=2;i<x/i;i++){
        int s=0;
        if(x%i==0){
            while(x%i==0){
                s++;
                x/=i;
            }
            cout<<i<<" "<<s<<endl;
        }
    }
    if(x>1)
        cout<<x<<" "<<1<<endl;

    return 0;
}
```

![[image-174fd0eb.png]]

至于为什么是wa 而不是tle

其实是数据类型爆了 第二组数据直接要算100的阶乘 试问用什么数据类型来存呢

显然先算阶乘再做分解是不可行的

有什么办法不做阶乘 还能进行分解？

这其实就是引入了一个新的质因数分解的方式

一般做组合数的题目都要进行质因数的分解，我们一般是for循环对每个数进行质因数分解，大多数情况都不会超时，但极少数的情况下，题目会不允许这样的做法，所以我们需要学会一种更快的方法来求质因数。

我们一般的方法是对每个数进行质因数分解：

```cpp
for(int i=2;i<=n/i;i++){
    while(n%i==0){
        h[i]++,n/=i;
    }
}
if(n>1)
   h[n]++;//大于sqrt(n) 的质因子 要么没有 要么只有一个
```

如果要做到更快的分解 可以直接对n!进行分解

比如求8!中2的倍数 原本是算出8! 然后while去模上2 就可以得到2的数量 2作为底数 数量作为指数

不妨把表打出来

1 2 3 4 5 6 7 8 我们求得在8！中2的个数

   1    1     1    1 首先我们先计算出2的倍数的个数：8/2=4

       1          1 其次计算出4的倍数的个数：
8/4=2（上面求出了第一层，现在求第二层）

                   1
最后我们解出第三层的2的个数： 8/8=1

我们把4+2+1=7，所以一共7个2出现了。

**即：cnt(x)=[n/(x^1)]+[n/(x^2)]+[n/(x^3)]+…(直到x的次方大于n)**

到这里我们可以发现：我们平时求的方法是**一列一列**求的（就是每一个数算一遍），而这个方法我们**每一行每一行**的求，虽然效果一样，但求起来速度很快。值得学习。

故做法：

　　1.先把素数表打好

　　2.for循环把小于n的每个质数进行一次运算，用数组记录

　　3.结束

非常快

![[image-35a9ff66.png]]

```cpp
void factorize_factorial(int n, const set<int>& primes) {
    for (int p : primes) {
        if (p > n)
            break;
        int count = 0;
        for (long long k = p; k <= n; k *= p) {
            count += n / k;
        }
        cout << p << " " << count << endl;
    }
}
```

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
bool isnot_prime[2*N];

set<int> get_primes(int n){
    set<int> primes;
    for(int i=2;i<=n;i++){
        if(!isnot_prime[i]){
            primes.insert(i);
            for(int j=i;j<=n;j+=i)
                isnot_prime[j]=true;
        }
    }
    return primes;
}

// 计算N!的质因数分解
void factorize_factorial(int n, const set<int>& primes) {
    for (int p : primes) {
        if (p > n)
            break;
        int count = 0;
        for (long long k = p; k <= n; k *= p) {
            count += n / k;
        }
        cout << p << " " << count << endl;
    }
}

int main() {
    int N;
    cin >> N;
    auto primes = get_primes(N);
    factorize_factorial(N, primes);
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[质数距离|质数距离]] 🏠 [[00-刷题理模型]] ➡️ [[质数问题|质数问题]]