数学思路

最近要开始学一些数学方面的东西了，这题作为基础题再好不过了。首先，这道题问的就是在阶乘\(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;
}

背景

自从NOIp 2018初赛第一次知道有数学期望这个东西起，我就一直很难理解。我一直没有去仔细的了解数学期望，而今天打了一场比赛，被逼着去了解了，现在我来写点东西记录一下这个概念。

概念介绍

\(数学期望\)是一个跟概率相关的概念。他的定义是：

数学期望是一个有限的事件的结果乘上一个事件的概率。

我们可以通过举例子来解释这个概念。比如取一个随机数（1-10之间），那么取到5的数学期望就是\(\frac {1} {2}\)。一般，我们用\(\mathbb{E}\)来表示这个值。

性质介绍

在本篇文章中，我只介绍一个性质。未来如果我学到了一些关于数学期望的新东西，那么我会把这些内容写在这篇文章里的。

数学期望在OI中比较重要的性质就是其线性性。简单来讲，如果有两个事件的数学期望为\(\mathbb{E}(a)\)和\(\mathbb{E}(b)\)，那么这两个事件叠加起来就是\(\mathbb{E}(a) + \mathbb{E}(b) = \mathbb{E}(a+b)\)。这个性质在OI中比较重要，一些题目会利用这个性质让解题者使用递推的方式解出答案。接下来我们看一道题目：

例题

链接：T2062:随机数生成器

这道题目是我在华南师范大学附属中学举办的比赛中遇到的题目。虽然我这一题并没有AC，但是不妨碍我们来解释数学期望的一些性质和递推得解的方法。

我们来思考这样一个方程，设置\(\mathbb{E}(i)\)为输入为\(i\)的数学期望，那么，根据数学期望的线性性质，我们可以很容易推出以下方程：\[\mathbb{E}(i) =\frac {\mathbb{E}(1) + 1}{i} + \frac {\mathbb{E}(2) + 1}{i} + \frac {\mathbb{E}(3) + 1}{i} + \frac {\mathbb{E}(4) + 1}{i} + \dots + \frac {\mathbb{E}(i) + 1}{i}\]

而在本题中，可知\(\mathbb{E}(1) = 0\)。那么我们来变换一下式子，变成：\[\mathbb{E}(i) = \frac {\mathbb{E}(1) + \mathbb{E}(2) + \dots + \mathbb{E}(i – 1) + i}{n – 1}\]这样我们就可以递推出式子。

数学期望是OI中常见的概念，掌握它很有帮助。建议读者可以自己去阅读相关的资料，我在这里便不再描述。