? ? ? ?万里之行，始于足下。本博客总结暑期学习到的部分数论模板，以便于日后查询使用。作者水平有限，难免存在疏漏不足，恳请诸位看官斧正。倘若我的文章可以帮到你，十分荣幸。感谢18级学长lyh和19级学长lyk两位提供的灵感。
? ? ? 哈？你问我图论的spfa、dijkstra和Kruskal算法啥的什么时候写？TAT
目录
2.高斯—若尔当消元法（Gauss-Jordan Elimination）
1.快速幂
? ? ?平时我们要求x的n（n较大）次方该如何用代码实现？
int ans=1;
for(int i=1;i<=n;i++)
{
ans*=x;
}//cyh的做法? ? ?这种做法没有错，但时间复杂度为O（n） ，导致在面对大数的时候可能会花费太多时间。
pow(x,n);//zmh:哈哈哈我会用函数? ? ?注意：pow的返回值为double类型，在计算较大数时会产生浮点误差！
? ? ?这里会介绍两种快速幂的实现：递归和位运算。如题：洛谷-P1226 【模板】快速幂||取余运算
1.递归实现快速幂
? ??
typedef long long ll;
ll qpow(ll x, ll n)
{
if(n==0)
{
return 1;
}
else if(n%2==1)
{
return qpow(x,n-1)*x%mod;//mod为取余的数
}//奇数次幂就单独拎出来一个x乘
else
{
ll ans=qpow(x,n/2)%mod;
return ans*ans%mod;
}//偶数次幂，掰开n对半乘
}? ? ? ?用递归的的方法，将大数二分。
2.位运算实现
? ? ? ?嘛，递归虽然挺清晰的，但是会占用大量栈空间，而且递归会慢于非递归算法，这里建议第二种使用位运算的算法。我们可以把n写成二进制的形式，通过二进制数的不断移位，同时取x平方来实现运算。
typedef long long ll;
ll qpow(ll x,ll n)
{
ll ans=1;
x%=mod;//mod还是取余数
while(n)
{
if(n&1)//判断n的是否为奇数
{
ans=ans*x%mod;
}
x=x*x%mod;
n>>=1;
}
return ans;
}2.矩阵消元
? ? ? ? 在求多元一次方程解或逆矩阵时，我们常常会使用矩阵的消元；消元法解线性方程组过程实际上是对方程组未知数的系数和常数项作有限制的运算，未知变量并未参与运算。因此，将解线性方程组的消元运算移植到矩阵变换中就是对线性方程组的增广矩阵进行三种初等变换并化简为行阶梯矩阵或者行最简形矩阵。
1.高斯消元（Gaussian Elimination）
? ? ? ?具体消元步骤相信聪明的你一定知道，在此不做赘述。如题：洛谷-P3389 【模板】高斯消元法?上代码：
#include <bits/stdc++.h>
using namespace std;
double a[105][105],ans[105];
const double eps=1e-7;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n+1;j++)
{
cin>>a[i][j];
}
}//输入矩阵
for(int i=1;i<=n;i++)
{
int temp=i;
for(int j=i+1;j<=n;j++)
{
if(fabs(a[temp][i])<fabs(a[j][i]))
{
temp=j;
}
}
if(fabs(a[temp][i])<eps)
{
cout<<"No Solution";
return 0;
}//当前列最大值为0，无解
if(i!=temp)
{
swap(a[i],a[temp]);
}//与最大主元所在行交换
double mul=a[i][i];
for(int j=i;j<=n+1;j++)
{
a[i][j]/=mul;
}
for(int j=i+1;j<=n;j++)
{
mul=a[j][i];
for(int k=i;k<=n+1;k++)
{
a[j][k]-=a[i][k]*mul;
}
}
}//消元过程
ans[n]=a[n][n+1];
for(int i=n-1;i>=1;i--)
{
ans[i]=a[i][n+1];
for(int j=i+1;j<=n;j++)
{
ans[i]-=(a[i][j]*ans[j]);
}
}//回带过程
for(int i=1;i<=n;i++)
{
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans[i]<<endl;//输出
}
}? ? ? ? ? 高斯消元法的时间复杂度为O（n^3）。
2.高斯—若尔当消元法（Gauss-Jordan Elimination）
? ? ? ? 高斯-若尔当消元法和高斯消元类似，不同的是高斯-若尔当消元法是将矩阵最终转化为行最简矩阵。
?
? ? ? ? 如题：洛谷-P4783 【模板】矩阵求逆?上代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[405][810];
const ll mod=1e9+7;
bool sign=1;
ll qpow(ll x,ll n)
{
ll ans=1;
x%=mod;
while(n)
{
if(n&1)
{
ans=ans*x%mod;
}
x=x*x%mod;
n>>=1;
}
return ans;
}
void gj()
{
for(int i=1;i<=n;++i)
{
int temp=i;
for(int j=i+1;j<=n;j++)
{
if(a[j][i]>a[temp][i])
{
temp=j;
}
}
if(temp!=i)
{
swap(a[i],a[temp]);
}
if(!a[i][i])
{
sign=0;
return ;
}
ll m=qpow(a[i][i],mod-2);
for(int k=1;k<=n;k++)
{
if(k==i)
{
continue;
}
ll p=a[k][i]*m%mod;
for(int j=i;j<=(n<<1);j++)
{
a[k][j]=((a[k][j]-p*a[i][j])%mod+mod)%mod;
}
}
for(int j=1;j<=(n<<1);j++)
{
a[i][j]=(a[i][j]*m%mod);
}
}
}//类似于高斯消元法
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n ;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
a[i][i+n]=1;
}
}
gj();
if(sign)
{
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=(n<<1);j++)
{
cout<<a[i][j];
if(j<(n<<1))
{
cout<<' ';
}
}
if(i<n)
{
cout<<endl;
}
}
}//逆矩阵输出
else
{
cout<<"No Solution";
}
return 0;
}? ? ? ? 高斯-若尔当消元法类似于高斯消元。但是需要注意多存一个单位矩阵。
3.矩阵的乘法与快速幂
? ? ? ? 在看过了矩阵消元之后，我们不妨想一想，矩阵之间的乘该如何实现？啥？矩阵也有快速幂？如题：洛谷-P3390 【模板】矩阵快速幂?上代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,k;
struct Matrix
{
int n,m;//矩阵行列数
ll matrix[105][105];//矩阵的“内容”
Matrix(int x,int y)
{
n=x,m=y;
memset(matrix,0,sizeof(matrix));
}//构造函数初始化
};//利用结构体存储矩阵
Matrix mul(Matrix a,Matrix b)
{
Matrix ans(a.n,b.m);
for(int i=1;i<=ans.n;i++)
{
for(int j=1;j<=ans.m;j++)
{
for(int k=1;k<=a.m;k++)
{
ans.matrix[i][j]+=a.matrix[i][k]*b.matrix[k][j]%mod;
ans.matrix[i][j]%=mod;
}
}
}
return ans;
}//矩阵乘法的实现
Matrix qpow(Matrix m,ll x)
{
Matrix ans(n,n);
memset(ans.matrix,0,sizeof(ans.matrix));
for(int i=1;i<=n;i++)
{
ans.matrix[i][i]=1;
}
while(x)
{
if(x&1)
{
ans=mul(ans,m);
}
m=mul(m,m);
x>>=1;
}
return ans;
}//矩阵快速幂
int main()
{
cin>>n>>k;
Matrix M(n,n);
M.m=n,M.n=n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>M.matrix[i][j];
}
}
M=qpow(M,k);//矩阵快速幂
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<M.matrix[i][j];
if(j<n)
{
cout<<' ';
}
}
if(i<n)
{
cout<<endl;
}
}//答案矩阵的输出
return 0;
}? ? ?? 矩阵的乘法在此不做过多赘述，我相信聪明的你一定可以看懂它的代码实现。会了矩阵乘法，至于矩阵快速幂，我们不妨和上面第一节的家伙比一比就很清晰了。
? ? ? “山再高，往上攀，总能登顶；路再长，走下去，定能到达。”路漫漫其修远兮，吾将上下而求索，共勉！?