Acwing197.阶乘分解

阶乘分解也是一道非常经典的题目，涉及到一个重要结论

如果我们想将x!分解质因数为

x! = \prod {p_i}^{\alpha _i}

的形式，那么对于任意一个质因子p_i的次数\alpha _i，有

\alpha _i = \sum_{i=1}^{\infty } \left \lfloor \frac{x}{p^i}  \right \rfloor 

不难看出和式到某一项之后因为分母大于分子，所以值为零，也就是说在程序中我们只需做到当前项为零就停止累加即可

该结论的一个不严谨理解方法可以用Excel来表示

该图的基本思路是，将10!分解成1098765432*1的形式，然后在其中挑出2的倍数的个数（第一层），累加，再挑出4的倍数的个数（第二层），累加，然后以此类推，每次累加一层直至不能为止

如果写成函数的形式可以这样

int get_power(int x, int p)
{
    // 返回x!中质数p为因子的次数
    // 公式: 次数 = [x / p] + [x / p ^ 2] + [x / p ^ 3] + ^
    int res = 0;
    while(x)
    {
        res += x / p;
        x /= p;
    }
    return res;
}

本题的做法便是先用质数筛处理出小于n的所有质数，然后对每个质数p求出在n!中p作为质因子的指数 完整代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int primes[N], idx[N]; // primes是质数表，idx存对应质数表的指数
bool v[N];
int initPrimes(int n)
{
    // 线性筛（也叫欧拉筛）模板，处理出n以内的质数并且返回个数
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!v[i])   primes[++cnt] = i;
        for(int j = 1; primes[j] <= n / i; j++)
        {
            v[primes[j] * i] = true;
            if(i % primes[j] == 0)  break;
        }
    }
    return cnt;
}

int main()
{
    int n;
    scanf("%d", &n);

    int cnt = initPrimes(n);

    for(int i = 1; i <= cnt; i++)
    {
        int p = primes[i];
        int tempN = n, pw = 0;
        while(tempN)
        {
            pw += tempN / p;
            tempN /= p;
        }
        if(pw)
        {
            printf("%d %d\n", p, pw);
        }
    }

    return 0;
}