数学问题模板 - 记录

# 筛选质因子

	for(int i=2;i*i<=k;i++){
	if(k%i==0){
	p[++tail]=i; //p 就是储存质因子的数组
	while(k%i==0) k/=i; // 把 k 中所有 i 的质因子全部除去
	}
	}
	if(k>1) p[++tail]=k;

# 判断是否为质数

	bool isp(int n){
	if(n==1\|\|n==0) return 0;
	if(n==2\|\|n==3) return 1;
	if(n%6!=1&&n%6!=5) return 0;
	for(int i=5;i*i<=n;i+=6){
	if(n%i==0\|\|n%(i+2)==0) return 0;
	}
	return 1;
	}

# 容斥原理

前言：

计算 1-n 中 m 的的倍数的数量时，直接 n/m
容斥原理是在互质的数的基础上实现的
公式：

(A+B+C+D+E……)-(AB+AC+AD……+BC+BD)+(ABC+BCD……)-(ABCD+BCD*E……)……

规律：奇数相加，偶数相减

代码：

	p数组储存的是筛选的质因子
	long long fun(long long x){
	long long res=0; //res 储存的是 1-x 中与 K 不互质的数量
	for(int i=1;i<(1<<tail);i++){ // 这里的 1<<tail 是指 2 的 tail 次方，表示 tail 个质因子有多少种组合情况
	long long cur=1,cnt=0; //cur 表示在当前选中的质因子中的乘积，cnt 表示当前选中的数量是奇数还是偶数
	for(int j=0;j<tail;j++){ // 这个循环是枚举 tail 的二进制形式
	if((i>>j)&1){ // 这个是判断 i 的第 j 位是不是 1，如果是则表示选中第 j 个数
	cnt++; // 表示选中了几个数，每选中一个就加一
	cur*=p[j+1]; // 选中第 j 个数就用 cur 乘以第 j 个质因子数，注意质因子数组是从 1 开始的，所以要加一
	}
	}
	if(cnt&1) res+=x/cur; // 如果 cnt 是偶数就相加
	else res-=x/cur; // 奇数就相减
	}
	return x-res; //res 储存的是 1-x 中与 K 不互质的数量，所以要用 x-res 得到互质的数量
	}

# 欧拉筛

	int vis[maxn],p[maxn/10]; // 质数密度不大，除以 10 可以减少空间浪费
	int cnt=0;
	void prime()
	{
	vis[1]=1;
	for(int i=2;i<=maxn;i++){
	if(!vis[i]) p[++cnt]=i;
	for(int j=1;j<=cnt&&i<=maxn/p[j];j++){
	vis[i*p[j]]=1;
	if(i%p[j]==0) break; // 核心代码，如果 i 能整除这个质数则跳出循环
	}
	}
	}

# 埃式筛

	int p[1000]; //p 数组用来存储质数
	void prime()
	{
	vis[1]=1; //1 不是质数
	for(int i=2;i<=n;i++){ //n 是筛选的范围
	if(!vis[i]){
	p[++cnt]=i; // 存储质数
	for(int j=2i;j<=n;j+=i){ // 这里可以有一个优化，j=2i
	vis[j]=1; // 标记质数的倍数
	}
	}
	}
	}

# 数学公式

海伦公式
S=sqrt (p * (p-a) * (p-b) * (p-c))

# 快速幂

非递归版本

int p(int a,int b){
  int t,y;
  t=1; y=a;
  while (b!=0){
    if (b&1==1) t=t*y%MOD;
    y=y*y%MOD;
    b=b>>1;
  }
  return t;
}

递归版本

	ll pow(ll a,ll i){
	if (i==0) return 1;
	ll temp=pow(a,i>>1)%MOD;
	temp=temp*temp%MOD;
	if (i&1) temp=temp*a%MOD;
	return temp%MOD;
	}

# 龟速乘 (快速幂 BUG)

	ll gsc(ll a,ll b){
	ll ans=0;
	while(b){
	if(b&1) ans=(ans+a)%MOD;
	a=a*2%MOD;
	b>>=1;
	}
	return ans;
	}

# 快速乘 (有误差)

	cin>>a>>b>>mod;
	cout<<((ab-(long long)((long double)ab/mod)*mod+mod)%mod);

# 树状数组模板

	int lowbit(int n){
	return n&-n;
	}

	void add(int x,int y,int n){
	for(int i=x;i<=n;i+=lowbit(i))
	c[i] += y;
	}

	int getsum(int x){
	int ans = 0;
	for(int i=x;i;i-=lowbit(i))
	ans += c[i];
	return ans;
	}

# 查并集

	void init(int n) {
	for(int i = 1; i <= n; i++) {
	f[i] = i;
	}
	}

	int getFriend(int v) {
	if(f[v] == v) {
	return v;
	}
	return f[v] = getFriend(f[v]);
	}

	void merge(int a, int b) {
	int t1 = getFriend(a);
	int t2 = getFriend(b);
	if(t1 != t2) {
	f[t2] = t1;
	}
	}

# 快速排序

	// 左右都是闭区间
	int qsort(int l,int r,int *v){
	int mid=(l+r)>>1;
	int i=l,j=r;
	int temp=v[mid];// 基准值是会被交换的，必须备份
	while(i<=j){// 这里小于等于都行
	while(v[j]>temp) j--;// 找到第一个小于等于基准值的
	while(v[i]<temp) i++;
	if(i<=j){ // 这里必须是小于等于，因为当只有两个数时，两个指针一定会重合
	swap(v[i],v[j]);
	i++; j--;// 这里必须，因为当交换的两个数有基准值时，若没有这一步，两个指针必然重合，然后会无限重复
	}
	}
	//i 一定比 j 大，排序过后 i 左面都小于基准值，j 右面都大于基准值就找到了基准值的位置
	if(i<r) qsort(i,r,v);// 再排基准值右面
	if(j>l) qsort(l,j,v);// 再排基准值左面
	}

# 组合数打表 (杨辉三角)

int类型最多到33层，34层开始爆int，ll最多50层左右，打表最多1e3的量

	int c[50][50];
	int zuhe(){// 下标从 0 开始
	c[0][0]=1;
	c[1][0]=1;c[1][1]=1;
	for(int i=2;i<=33;i++){
	c[i][0]=1;
	for(int j=1;j<=i;j++){
	c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	}
	}

持续更新中……

数学问题记录

# 筛选质因子

# 判断是否为质数

# 容斥原理

# 欧拉筛

# 埃式筛

# 数学公式

# 快速幂

# 龟速乘 (快速幂 BUG)

# 快速乘 (有误差)

# 树状数组模板

# 查并集

# 快速排序

# 组合数打表 (杨辉三角)

如何给Hexo博客添加说说页面

数状数组求逆序对&&二维树状数组