数论及模板

文章首发于：My Blog 欢迎大佬们前来逛逛

求两个正整数的最大公约数

时间复杂度：O（NlogN）

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

---

线氏筛求质数

时间复杂度：O（N）

int nums[N];
void get_primes(int n){
    bool vis[N];
    int cnt=0;
	for (int i=2;i<=n;i++){
        if (!vis[i]){
            nums[cnt++]=i;
        }
        for (int j=0;nums[j]*i<=n;j++){
            vis[nums[j]*i]=true;
            if (i%nums[j]==0){
                break;
            }
        }
    }	
    //nums;
}

196. 质数距离

196. 质数距离

---

求出在【L，R】区间内某两个质数分别是距离最小的和距离最大的。

性质一 ： 数字N如果是一个合数，则N一定存在一个小于等于sqrt(N)的质因子。

假设a和b是N的两个质因子，则ab=N，假设 a<=b，则 a a <= a * b = N，则可以得出：a<=sqrt(N)

性质二： 如果x属于【L，R】的区间中合数，则一定存在一个p值，满足p<=sqrt(N)，并且这个p值 是x的一个质因子，则便可以通过 p 值来筛选出在【L，R】区间中的每一个合数。

---

步骤：

1. 预处理质数：首先由于数据都是小于 2^31-1 的，因此最大的质因子为 sqrt(2^31 -1 )，粗略计算大概是50000，则我们只需要预处理出[1,50000] 的质数即可。
2. 筛出合数：然后根据 [1,50000]之间的质数 p，通过遍历p的倍数，来筛出 [L,R]区间中所有的合数，则剩下的就一定全部都是质数。
3. 寻找距离：然后在剩下的质数数组中寻找相邻的两个数字的距离最小和最大的。

---

细节：【x】表示上取整x

1. 在筛出合数的过程中，我们需要找到[L,R]区间中所有的合数，因此对于每一个枚举的p，都需要首先找到大于等于L的第一个初始的位置，然后在i<=r的条件下每次+=p，这样这些位置标记的都是合数。
2. 对于这个初始的位置，我们应该取得[L,R]的第一个合数，具体的做法为：
   • 如果初始的p不在[L,R]的区间内：初始的位置应该是【L/p】*p.
   • 如果初始的p在[L,R]的区间内：初始的位置至少为2*p，因为p是需要循环的第一个质数，2*p是第一个合数

如何表示 2 过程的上取整呢？公式如下：

$$\left \lceil \frac{L}{P} \right \rceil\times P => (\frac{L-1}{P}+1) \times P$$

因此对于上面的描述过程，我们可以这样描述：

for (int i=1;i<=cnt;i++){
	int p=nums[i];//取得这个初始的p值
	for (int j=max((L-1)/p+1)*p,2*p);j<=r;j+=p){//在[L,R]内寻找p的倍数，他们都是合数
		//标记合数
	}
}

完整代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <limits.h>
using namespace std;
const int N = 1e6+10;
#define int long long
int l,r;
int nums[N],cnt;
bool temps[N];
//线氏筛求质数: O(N)
void get_num(int n){
    memset(temps,0,sizeof(temps));
    for (int i=2;i<=n;i++){
        if (!temps[i]){
            nums[cnt++]=i;
        }
        for (int j=0;nums[j]*i<=n;j++){
            temps[nums[j]*i]=true;
            if (i%nums[j]==0){
                break;
            }
        }
    }
}
signed main()
{
    //预处理质数
    while (cin>>l>>r){
        get_num(50000);
        /*
        如果N是一个合数，则N一定存在一个小于等于sqrt(N)的质数：
            假设a和b是N的两个质数，并且假设a<=b，则 a*a <= a*b = N， 则 a<=sqrt(N)，a就是N的一个小于等于sqrt(N)的质数
        */
        //1. 首先筛出[1,50000]之间所有的素数
        //2. 把 [L,R]范围内的所有的合数“删除”掉，则剩下的就是目标范围内的质数
        memset(temps,0,sizeof(temps));
        for (int i=0;i<cnt;i++){
            int p=nums[i];//取得每一个[1,50000]之间的质数，对这个数字取倍数，则生成的数字一定是合数
            for (int j=max((l-1)/p+1)*p,2*p);j<=r;j+=p){
                temps[j-l]=true; //相当于离散化，防止数组下标过大，减去左边界
            }
        }
        cnt=0;
        for (int i=0;i<=r-l;i++){
            if (!temps[i] && i+l>1){
                nums[cnt++]=i+l;//再加上l，就变成了原数
            }
        }
        if (cnt<2){
            cout<<"There are no adjacent primes.\n";
        }
        else{
            //获得答案
            int minp=0,maxp=0;
            for (int i = 0; i+1 < cnt; i ++ ){
                int d=nums[i+1]-nums[i];
                if (d<nums[minp+1]-nums[minp]){
                    minp=i;
                }
                if (d>nums[maxp+1]-nums[maxp]){
                    maxp=i;
                }
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",nums[minp],nums[minp+1],nums[maxp],nums[maxp+1]);
        }
    }
    return 0;
}

---

求组合数

求组合数：C(n,k)，即在 n个数字中选择k个数字。

int C[N][N];
void get(){
	for (int i=0;i<=n;i++){
		for (int j=0;j<=i && j<=k;j++){ //小于等于k为一个小优化
			if (!j) C[i][j]=1; //j为零的时候初始化，即C(i,0)=1
			else C[i][j]=C[i-1][j-1]+C[i-1][j]; //类似于杨辉三角
		}
	}
}

通过这种方式得到C(n,k)的值：C[n][k]

时间复杂度：O（N^2）

---

快速幂

计算X ^ N % mod的值

模板代码如下：

#define int long long
int x,n,mod=9999999;
int get(){
	int ans=1;//初始化为1
	for (;n;n>>=1){
		if (n&1){
			ans=ans*x%mod;
		}
		x=x*x%mod;
	}
    return ans;
}

---