十、常用数学知识

绿色：需要掌握了解；红色：需要会写会用或很重要。

本章节主要介绍模拟一些基础的数学公式和定理的方法。

①素数②欧几里得算法（辗转相除法）③分数④大整数计算

补充：①基姆拉尔森计算公式②错排公式③约瑟夫环相关公式

素数

1.判断素数

最简单的方法就是判断从2到sqrt(N)中是否有N的因数，代码如下：

注意，循环条件中的【(int)sqrt(n)】不建议写作【i*i<=n】，因为实际运行过程中可能会因数据溢出造成错误。

2.获取2~n以内的素数表

①埃拉托斯特尼筛法（简称为埃氏筛法），其算法逻辑是把不大于n的所有素数的倍数剔除，剩下的就是素数，代码如下：

埃氏筛法的时间复杂度为O(NloglogN)，一般情况下足够使用了。

不难发现，代码中会出现同一数被反复筛去的情况（即质数乘出来的合数）。例如：2会筛去6，3也会筛去6。因此下面引入欧拉筛法。

②欧拉筛法，算法逻辑为筛去素数乘以所有不大于其的素数的乘积，理论上不会出现重复筛去的情况，代码如下：

理论上，欧拉筛法的时间、空间复杂度皆为O(N)。对欧式筛法正确性和时间复杂度证明感兴趣可以参考https://blog.csdn.net/qaqwqaqwq/article/details/123587336。

3.对n进行质因数分解

一个数的质因子在分解后可能不止出现一次，因此可以使用关联容器map或者unordered_map来存储质因子，其中键表示质因子，值表示该质因子出现的次数。若题目要求对质因子排序，则使用map，否则使用unordered_map。

欧几里得算法（辗转相除法）

欧几里得算法基于定理：，用于求a与b的最大公约数，代码如下：

可以看出当a<b时，可以将a和b交换；当a>b时，该定理可以将数据的规模变小，而且减小的速度非常快，因此也不必担心递归时的递归爆栈。

在求得两数的最大公约数后，这两个整数的最小公倍数就可以求出。即若，则a和b的最小公倍数为。在代码实现的过程中，你应该使用而不是，因为在计算a*b时容易造成数据溢出。

分数

分数最简单的表示方法就是写成假分数的形式，因为只需分子分母两个整数即可，因此可以用array<int,2>来表示这样一个假分数。

1.分数的化简

2.分数的输出

大整数运算

1.大整数加法

2.大整数减法

3.大整数乘法

4.大整数除法

※ 不必刻意记忆上述算法，只需理解代码后注意在加减法中结果字符串需要翻转，在减法、乘法、除法运算中结果字符串需要去除前导0。

补充一些数学公式定理

①基姆拉尔森计算公式（用于求解指定的年月日是星期几）

注意：区别于其他公式，该公式中把1月和2月看成是上一年的13月和14月。例如，2004-01-10应当换算成2003-13-10再代入公式计算。

②错排公式/重排公式

n个有序的元素应有n!个不同的排列，若一个排列中所有的元素都不在其原来的位置上，则称这个排列为错排或称重排。例如：12的错排是唯一的，即21。123的错排有312、231。这二者可以看作是12错排，3分别与1、2换位而得的。

★★为求错排问题解法的递推关系，分两步走：

    第一步，考虑第n个元素，把它放在某一个位置，比如位置k，共有n-1种放法；

    第二步，考虑第k个元素，这时有2种情况：

        1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有种放法；

        2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有种放法。

★★综上，根据乘法和加法法则可得：。

★★特殊的，。

Dn的通项公式为：Dn=nD_{n-1}+(-1)^n。

③约瑟夫环相关公式

问题描述：将编号为0～（N–1）这N个人进行圆形排列，按顺时针从0开始报数，报到M–1的人退出圆形队列，剩下的人继续从0开始报数，不断重复。求最后出列者最初在圆形队列中的编号。这类特定问题，可以看成递归，但是其递归公式可能较难推出，推导可见此处。

★下面直接给出得到的递归公式（假设编号从0开始，F(N)表示N个人中退出的人的编号）：

★★ 

★★ 

下面分别给出约瑟夫环的递归和递推写法：