CH3101:阶乘分解题解

数学思路

最近要开始学一些数学方面的东西了,这题作为基础题再好不过了。首先,这道题问的就是在阶乘\(N!=1*2*3*\dots *N\)中分解质因数。我们可以先求出\([1,N]\)范围内的质数,然后再来求出这个式子中质因数的次数。

memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i <= n; i++)
    if (isPrime[i])
    {
        primes.push_back(i);
        for (int factor = 2; factor * i <= n; factor++)
            isPrime[i * factor] = false;
    }

接下来,我们可以说明,在阶乘式中,对于一个素数\(p\),它的一次项出现次数为\( \lfloor \frac {N} {p} \rfloor \),则二次项出现的次数为\(\lfloor \frac {N} {p^2} \rfloor\),归纳起来,可以得到:

\[ \lfloor \frac {N} {p} \rfloor + \lfloor \frac {N} {p^2} \rfloor + \lfloor \frac {N} {p^3} \rfloor + \dots + + \lfloor \frac {N} {p^{log_{p} N}} \rfloor\]

化为循环式,得到:

\[ \sum_{p^i \leq N}^{i = 1} \; \lfloor \frac {N} {p^i} \rfloor\]

详细看代码吧:

// CH3101.cpp
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#define uint unsigned int
using namespace std;
const int MX_N = 5e6 + 100;
bool isPrime[MX_N];
uint n, cs[MX_N];
vector<uint> primes;
int main()
{
    scanf("%u", &n);
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        if (isPrime[i])
        {
            primes.push_back(i);
            for (int factor = 2; factor * i <= n; factor++)
                isPrime[i * factor] = false;
        }
    int siz = primes.size();
    for (int i = 0; i < siz; i++)
    {
        uint c = 0;
        for (int num = n; num; num /= primes[i])
            c += num / primes[i];
        printf("%u %u\n", primes[i], c);
    }
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注