AcWing 197. 阶乘分解

一.题目链接

二.思路

数据范围：$3\le N\le 10^6$
首先暴力方法，把N的阶乘算出来再进行分解质因数，此方法时间复杂度太过于庞大且超过long long需要使用高精度，非常麻烦。
$N!=1\ast 2\ast 3\ast ....\ast N$，我们将其分解质因数得$N!=p_1^{a_1}\ast p_2^{a_2}\ast p_3^{a_3}\ast ...\ast p_k^{a_k}$。我们可以将1,2,3，…，n分别分解质因数即可得到答案。但是时间复杂度也很大，每一次分解质因数都是$O(\sqrt{N})$的复杂度。所以我们考虑把每一个数分解，不如反方向考虑，考虑每一个数的倍数。因此我们只需要预处理出$10^6$以内的质数，然后枚举每一个质数，求一下1~N中$p_i$的有多少个，$p_i^2$有多少个，$...p_k^k$有多少个。

三.代码

#include 
#include 
#include 

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    init(n);
    
    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int s = 0;//当前质数的次数
        for(int j = n; j; j /= p) s += j / p;
        cout << p << " " << s << endl;
    }
    return 0;
}
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

四.总结

• 当需要对一个阶乘分解质因数的时候，可以采用这种思路。