专栏文章

学习笔记-数学

YYGBC_
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzrga0
此快照首次捕获于
2025/12/01 18:13
3 个月前
此快照最后确认于
2025/12/01 18:13
3 个月前
查看原文

数学

通常以组合数学，数论及杂项等形式出现。

快速幂

用于在 O(log⁡n)O(\log n) 时间内求 ana^n 或是 an mod pa^n\bmod p 的解的情况。有分治和倍增两种写法，倍增更优。核心代码如下：
CPP
int fast_pow(int x,int p)
{
	int res=1;
	while(p){
		if(p&1) res=res*x%mod;
		x=x*x%mod, p>>=1;
	}
	return res;
}

int quick_pow(int x,int p)
{
	if(!p) return 1;
	int res=quick_pow(x,p>>1);
	res=res*res%mod;
	if(p&1) res=res*x%mod;
	return res;
}

欧几里得算法

欧几里得算法用于在 O(log⁡min⁡(a,b))O(\log \min(a,b)) 复杂度内求解 gcd⁡(a,b)\gcd(a,b) 的算法，其核心是：
gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)
核心代码如下：
CPP
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}

扩展欧几里德算法（exgcd）

用于求二元线性丢番图方程 ax+by=gcd(a,b)ax+by=gcd(a,b) 的一组解。
设
ax1+by1=gcd⁡(a,b)ax_1+by_1=\gcd(a,b) bx2+(a mod b)y2=gcd⁡(b,a mod b)bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)
可以得到
x1=y2,y1=x2−⌊ab⌋y2x_1=y_2, y_1=x_2-\lfloor \frac{a}{b} \rfloor y_2
递归求解即可。核心代码如下：
CPP
void ex_gcd(int a,int b,int &x,int &y)
{
	if(!b) { x=1; y=0; return ; }
	ex_gcd(b,a%b,y,x); y-=a/b*x;
}
用扩展欧几里得算法求出 ax+by=gcd(a,b)ax+by=gcd(a,b) 的特解后，求 ax+by=cax+by=c 的解如下：
  1. 记 d=gcd⁡(a,b)d=\gcd (a,b)，ax+by=gcd(a,b)ax+by=gcd(a,b) 的一组特解为 x0,y0x_0,y_0，在 ax0+bx0=dax_0+bx_0=d 两边同时乘以 cd\frac{c}{d}，得
cdax0+cdbx0=c\frac{c}{d}ax_0+\frac{c}{d}bx_0=c
  1. 得出 ax+by=cax+by=c 的一组特解 (x0,y0)(x_0,y_0) 为
{x0′=cdx0y0′=cdy0\begin{cases} x_{0}^{'}=\frac{c}{d}x_0 \\ y_{0}^{'}=\frac{c}{d}y_0 \end{cases}

模逆元

对于非零整数a,ma,m，如果存在 bb 使得 ab≡1mod  mab\equiv 1 \mod m，就称 bb 是 aa 模 mm 意义下的逆元。

扩展欧几里得算法

利用扩欧求解 ax+py=gcd(a,p)ax+py=gcd(a,p)。得到的 xx 模 mm 就是 aa 的逆元。

快速幂

由费马小定理可得对于 a⊥pa\perp p 有
ap−1≡1mod  pa^{p-1}\equiv 1 \mod p
所以 a−1 mod pa^{-1} \bmod p 等于 a(p−2) mod pa^(p-2)\bmod p，利用快速幂求解。

递推求一组逆元

对于素数 pp，有递推式
i−1≡−⌊pi⌋(p mod i)−1mod  pi^{-1}\equiv -\lfloor \frac{p}{i} \rfloor (p \bmod i)^{-1} \mod p
模板代码如下：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

int N,P;
int inv[3000005];

signed main()
{
	cin>>N>>P;
	inv[1]=1; cout<<1<<'\n';
	for(int i=2;i<=N;i++){
		inv[i]=(P-P/i)*inv[P%i]%P;
		cout<<inv[i]<<'\n';
	} 
}

矩阵

不会用。
给出矩阵定义，矩阵乘法，快速幂的模板。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int Mod=1e9+7;
int N,k;

struct Matrix{
	int mat[105][105];
	Matrix operator * (const Matrix &a) const{
		Matrix b;
		memset(b.mat,0,sizeof b.mat);
		for(int i=1;i<=N;i++) 
			for(int j=1;j<=N;j++) 
				for(int k=1;k<=N;k++)
					b.mat[i][j]=(b.mat[i][j]+mat[i][k]*a.mat[k][j])%Mod;
		return b;
	}
}A;

Matrix fast_pow(Matrix a,int p){
	Matrix res;
	memset(res.mat,0,sizeof res.mat);
	for(int i=1;i<=N;i++) res.mat[i][i]=1;
	while(p){
		if(p&1) res=res*a;
		a=a*a;
		p>>=1;
	}
	return res;
}

signed main()
{
	cin>>N>>k;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			cin>>A.mat[i][j];
	Matrix res=fast_pow(A,k);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) cout<<res.mat[i][j]<<' ';
		cout<<'\n';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...