type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
求两个正整数的最大公约数
时间复杂度：O（NlogN）
线氏筛求质数
时间复杂度：O（N）
196. 质数距离
求出在【L，R】区间内某两个质数分别是距离最小的和距离最大的。
性质一 ： 数字N如果是一个合数，则N一定存在一个小于等于sqrt(N)的质因子。
假设a和b是N的两个质因子，则，假设 ，则 ，则可以得出：
性质二： 如果x属于【L，R】的区间中合数，则一定存在一个p值，满足，并且这个p值 是x的一个质因子，则便可以通过 p 值来筛选出在【L，R】区间中的每一个合数。
步骤：
预处理质数：首先由于数据都是小于 2^31-1 的，因此最大的质因子为 sqrt(2^31 -1 )，粗略计算大概是50000，则我们只需要预处理出[1,50000] 的质数即可。
筛出合数：然后根据 [1,50000]之间的质数 p，通过遍历p的倍数，来筛出 [L,R]区间中所有的合数，则剩下的就一定全部都是质数。
寻找距离：然后在剩下的质数数组中寻找相邻的两个数字的距离最小和最大的。
细节：【x】表示上取整x
- 在筛出合数的过程中，我们需要找到[L,R]区间中所有的合数，因此对于每一个枚举的p，都需要首先找到大于等于L的第一个初始的位置，然后在
i<=r的条件下每次+=p，这样这些位置标记的都是合数。
- 对于这个初始的位置，我们应该取得[L,R]的第一个合数，具体的做法为：
- 如果初始的p不在[L,R]的区间内：初始的位置应该是
【L/p】*p. - 如果初始的p在[L,R]的区间内：初始的位置至少为
2*p，因为p是需要循环的第一个质数，2*p是第一个合数
如何表示 2 过程的上取整呢？公式如下：
因此对于上面的描述过程，我们可以这样描述：
完整代码如下：
求组合数
求组合数：
C(n,k)，即在 n个数字中选择k个数字。通过这种方式得到C(n,k)的值：
C[n][k]快速幂
计算
X ^ N % mod的值模板代码如下：
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/math_qs1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。