2022年8月学习记录

2022-12-15 链接修复

链接修复：文章跳转链接修复

算法

倍增

快速幂

// 计算 a^b%p
#include<iostream>
#define ll long long
using namesapce std;
int main(){
	int a,b,p,ans=1;
	cin>>a>>b>>p;
	while(b){
		if(b&1) ans=(ll)ans*a%p;
		a=(ll)a*a%p;
		b>>=1;
	}
	cout<<ans%p<<endl;
	return 0;
}

快速乘

矩阵快速幂

RMQ问题

RMQ问题是一个(一组？)经典的可以用倍增来解决的问题

ST表

给定一个长度为n的序列A[1···n]，有q次询问，每次询问给出x，y，回答A[x···y]中的最大值。（也可以是最小值，此处以最大值为例）通常n,q<=100000）

利用倍增解决RMQ问题的算法：ST（Sparse Table）算法

// 生成ST表
for(int i=1;i<=n;i++)st[i][0]=A[i];
for(int j=1;(1<<j)<=n;j++)
	for(int i=1;i+(1<<j)-1<=n;i++)
		st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);

// 计算A[x···y]中的最大值 O(1)
int query(int x,int y){
	int k=(int)(log(y-x+1)/log(2));
	int m=max(st[x][k]，st[y—(1<<k)+1][k]);
	return m; 
}

树上最近公共祖先

树上最近公共祖先，简称LCA，是关于树的一个非常基础的概念：
给定一棵有根树，一个点到根节点的路径上的所有点称为该点的祖先若点u同时是点x，y的祖先，那么u称为x，y的公共祖先。的所有公共祖先中，深度最大的点称为x，y的最近公共祖先。
另一种理解：x到y的路径上深度最小的点为x，y的最近公共祖先。

// O(logn)
int LCA(int x,int y){
	if(d[x]<d[y]) swap(x,y);
	for(int i=16;i>=0;i--)
		if(d[f[x][i]]>=d[y])
			x=f[x][i];
	if(x==y) return x;
	for(int i=16;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}

简单数论

欧几里得算法

// O(loga)

// 递归法
int gcd(int a,int b){
	if (b==0) return a;
	return gcd(b,a%b);
}
// 迭代法
int gcd(int a,int b){
	while(b!=0){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

拓展欧几里得

对于给定的两个整数a和b，必存在整数x和y，使得 ax+by=gcd(a,b)

// 计算 a*x+b*y=gcd(a,b) 的特解
void Extended_Gcd(int a,int b,int &d,int &x,int &y){
	if(0==b){
		d=a;
		x=c/a;
		y=0;
	}else{
		int x1,y1;
		Extened_God(b,a,d,x1,x2);
		x=y1;
		y=x1-a/b*y1;
	}
}

裴蜀定理

方程 ax+by=c 有整数解的充分必要条件是 c 是 gcd(a,c) 的倍数

素数

输入N（N<=5*10^7）,输出1到N之间的所有素数。

// O(nlnlnn)
void sieve(int n){
	memset(isPrime,true,sizeof(isPrime));			//#include<string.h>
	for{int i=2;i*i<n;i++}{
		if(isPrime[i]){
			for(int j=i*i;i<=n;i+=i){
				isPrime[j]=false;
			}
		}
	}
}

欧拉筛

// O(n)
void Euler_sieve(int n){
	memset(isPrime,true,sizeof(isPrime));			//#include<string.h>
	for{int i=2;i<=n;i++}{
		if(isPrime[i]) prime[++prime[0]]=i;
		for(int	j=1;i<=prime[0] && i*prime[j]<=n;j++){
			isPrime[i*prime[0]]=false;
			if(0==i%prinme[j]) break;
		}
	}
}