[数论]数论与与组合数学与线性代数中的常用算法总结

数论

欧几里得算法(gcd)

欧几里得算法又称辗转相除法,设两个数为a,b,则a,b最大公约数为gcd(a,b)=gcd(b,a%b)

证明

设a>=b, c = gcd( a, b), a = kc, b = jc,则k,j互素(否则c不为a,b最大公约数),则设 r = a % b,则a = mb + r,则r = a - mb = kc - mjc = ( k - mj ) c,因为k,j互素,则k-mj与j互素,gcd(a,b) = gcd(b,a%b)

应用

如果判断两个数是否互素(最大公约数为1),这时辗转相除法就方便得多。因为每一步都是取模,保证了数据减小的速度特别快。能够在很短时间内找到最大公约数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归版
int gcd(int a, int b) {
return b ? a : gcd(b, a%b);
}
//非递归版
int gcd(int a, int b) {
if (!a)
return b;
while (b) {
int temp = b;
b = a%b;
a = temp;
}
return a;
}

扩展欧几里得算法(exgcd)

若a , b 不全为 0,则存在整数 x,y 使得 gcd(a,b)=xa+yb
对于辗转相除法的最后一项,此时 b=0,则 gcd(a,b)=1a+0b,因为 gcd(a,b)=gcd(b,a%b)则有 xa+yb=x1b+y1(a%b) 。将等式右边变形,bx1+(a%b)y1=bx1+(a-(a/b)b)y1=ay1+b(x1-(a/b)y1)
则,x=y1,y=x1-(a/b)*y1 则可由后向前迭代得到 x,y

应用

对于扩展欧几里德定理的题,一般都需要进行一定的推导之后得到一个形式为xa+yb=c 的方程,然后根据 c 确定解是否存在,如果 c 可以被 gcd(a,b)整除,那么方程有解,否则方程无解。而且所得的解释不唯一的,对于一组解 x0,y0 则其所有解可以表示为x=x0+b/gcd(a,b)t,y-y0-a/gcd(a,b)t,t=0,+1,+2……一般会要求找出 x 或者 y 的最小正整数解,这个时候需要做一些调整。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a / b*y;
return d;
}

筛法求素数

筛素数的基本方法是用来筛选出一定范围内的素数

原理

利用素数只有1和本身两个约数,且约数一定不大于自身。首先筛掉1.剩下的数选择最小的数为素数,然后筛掉它范围内所有的倍数,以此类推,直到筛为空时结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isprime[N];//N 表示范围
int prime[N], cnt;
void f()
{
int i, j;
cnt = 0;
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
for (i = 2; i <= N; i++)
{
if (isprime[i])
{
prime[cnt++] = i;//记录素数
for (j = i*i; j <= N; j += i)//因为小于 i 的所有的倍数都被筛过,所以直接从 i*i 开始,从这里也可以看出,筛素数时到 N^0.5就可以了
isprime[j] = false;
}
}
}

快速幂

快速幂的目的就是做到快速求幂,假设我们要求a^b,按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(n)级别,快速幂能做到O(logn)。

原理

  假设我们要求a^b,那么其实b是可以拆成二进制的,该二进制数第i位的权为2^(i-1),例如当b==11时,a11=a(2^0+2^1+2^3)。11的二进制是1011,11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1,因此,我们将a¹¹转化为算 a2^0a2^1a2^3,也就是a1 a2 a8,原来算11次,现在算三次,但是这三项貌似不好求的样子….不急,下面会有详细解释。由于是二进制,很自然地想到用位运算这个强大的工具:&和>>。&运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶,x&1==1为奇。>>运算比较单纯,二进制去掉最后一位,不多说了,先放代码再解释。

1
2
3
4
5
6
7
8
9
10
int poww(int a, int b) {
int ans = 1, base = a;
while (b != 0) {
if (b & 1 != 0)
ans *= base;
base *= base;
b >>= 1;
}
return ans;
}

以b==11为例,b=>1011,二进制从右向左算,但乘出来的顺序是 a^(2^0)a^(2^1)a^(2^3),是从左向右的。我们不断的让base*=base目的即是累乘,以便随时对ans做出贡献。

  其中要理解base =base这一步:因为 base base==base2,下一步再乘,就是base2 base2==base4,然后同理 base4 base4=base8,由此可以做到base–>base2–>base4–>base8–>base16–>base32…….指数正是 2^i ,再看上面的例子,a¹¹= a1a2a8,这三项就可以完美解决了

矩阵快速幂

矩阵乘法

简单的说矩阵就是二维数组,数存在里面,矩阵乘法的规则:A*B=C

img

其中c[i][j]为A的第i行与B的第j列对应乘积的和,即:img

1
2
3
4
5
6
7
8
9
10
const int N=100;  
int c[N][N];
void multi(int a[][N],int b[][N],int n)//n是矩阵大小,n<N
{
memset(c,0,sizeof c);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]+=a[i][k]*b[k][j];
}

方法很简单,把快速幂算法中的乘法改成矩阵的乘法就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N=10;  
int tmp[N][N];
void multi(int a[][N],int b[][N],int n)
{
memset(tmp,0,sizeof tmp);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
tmp[i][j]+=a[i][k]*b[k][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
a[i][j]=tmp[i][j];
}
int res[N][N];
void Pow(int a[][N],int n)
{
memset(res,0,sizeof res);//n是幂,N是矩阵大小
for(int i=0;i<N;i++) res[i][i]=1;
while(n)
{
if(n&1)
multi(res,a,N);//res=res*a;复制直接在multi里面实现了;
multi(a,a,N);//a=a*a
n>>=1;
}
}

下面放一个求斐波那契数列的矩阵快速幂模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod = 10000;
const int maxn = 35;
int N;
struct Matrix {
int mat[maxn][maxn];
int x, y;
Matrix() {
memset(mat, 0, sizeof(mat));
for (int i = 1; i <= maxn - 5; i++) mat[i][i] = 1;
}
};
inline void mat_mul(Matrix a, Matrix b, Matrix &c) {
memset(c.mat, 0, sizeof(c.mat));
c.x = a.x; c.y = b.y;
for (int i = 1; i <= c.x; i++) {
for (int j = 1; j <= c.y; j++) {
for (int k = 1; k <= a.y; k++) {
c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod;
c.mat[i][j] %= mod;
}
}
}
return ;
}
inline void mat_pow(Matrix &a, int z) {
Matrix ans, base = a;
ans.x = a.x; ans.y = a.y;
while (z) {
if (z & 1 == 1) mat_mul(ans, base, ans);
mat_mul(base, base, base);
z >>= 1;
}
a = ans;
}
int main() {
while (cin >> N) {
switch (N) {
case -1: return 0;
case 0: cout << "0" << endl; continue;
case 1: cout << "1" << endl; continue;
case 2: cout << "1" << endl; continue;
}
Matrix A, B;
A.x = 2; A.y = 2;
A.mat[1][1] = 1; A.mat[1][2] = 1;
A.mat[2][1] = 1; A.mat[2][2] = 0;
B.x = 2; B.y = 1;
B.mat[1][1] = 1; B.mat[2][1] = 1;
mat_pow(A, N - 1);
mat_mul(A, B, B);
cout << B.mat[1][1] << endl;
}
return 0;
}

欧拉函数

φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中 p1, p2……pn 为 x 的所有质因数。

设 p 是素数 a 是一个正整数 φ(p^a)=p^a-p^a-1; m 与 n 互素 φ(mn)=φ(m)φ(n); φ(n)=n sum(1-1/pi)/pi 是与 n 的质因子n 为奇数时 φ(2n)=φ(n)。

模运算

基本的模运算

(a + b)mod n=((a mod n) + (b mod n))mod n;

(a - b)mod n=((a mod n) - (b mod n))mod n;

(a b)mod n=((a mod n) (b mod n))mod n;

数论4大定理

威尔逊定理

若p为质数,则p可整除(p-1)!+1。

欧拉定理

若n,a为正整数,且n,a互素,即gcd(a,n) = 1,则a^φ(n) ≡ 1 (mod n)

证明

设x(1),x(2),…,x(φ(n))是一个以n为模的简系,则ax(1),ax(2),…,ax(φ(n) )也是一个以n为模的简系(因为(a,n)=1)。

于是有ax(1)ax(2)…ax(φ(n) )≡x(1)x(2)…x(φ(n))(mod n),

所以a^φ(n) ≡ 1 (mod n)。

费马小定理

假如p是质数,若p不能整除a,则 a^(p-1) ≡1(mod p),若p能整除a,则a^(p-1) ≡0(mod p)。

若p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1。

证明

因为p是质数,且(a,p)=1,所以φ(p)=p-1。由欧拉定理可得a^(p-1) ≡1(mod p)。证毕。对于该式又有a^p ≡a(mod p),所以,费马小定理的另一种表述为:假如p是质数,且(a,p)=1,那么a^p ≡a(mod p)。

孙子定理(中国剩余定理)

高斯消元

高斯消元法,是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。利用矩阵化成的行阶梯型可以方便的得出未知数的解。

要用高斯消元,一般也会需要一定的推理,得出线性方程组,再利用高斯消元求解。

组合数学

排列组合

加法原理

加法原理:做一件事,完成它可以有 n 类办法,第一类办法的方法属于集合 A1,第二类办法的方法属于集合 A2,……,第 n 类办法的方法属于集合 An,那么完成这件事的方法属于集合 A1UA2U…UAn。

分类的要求 :每一类中的每一种方法都可以独立地完成此任务;两类不同办法中的具体方法,互不相同(即分类不重);完成此任务的任何一种方法,都属于某一类(即分类不漏)

乘法原理

乘法原理:做一件事,完成它需要分成 n 个步骤,做第一步有 m1 种不同的方法,做第二步有 m2 种不同的方法,……,做第 n 步有 mn 种不同的方法,那么完成这件事共有N=m1×m2×m3×…×mn 种不同的方法。

合理分步的要求,任何一步的一种方法都不能完成此任务,必须且只须连续完成这 n 步才能完成此任务;各步计数相互独立;只要有一步中所采取的方法不同,则对应的完成此事的方法也不同。

公式

排列的定义及其计算公式:从 n 个不同元素中,任取 m(m≤n,m 与 n 均为自然数,下同)个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m(m≤n)个元素的所有排列的个数,叫做从 n 个不同元素中取出m 个元素的排列数,用符号 A(n,m)表示。A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! 此外规定 0!=1

组合的定义及其计算公式:从 n 个不同元素中,任取 m(m≤n)个元素并成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合;从 n 个不同元素中取出 m(m≤n)个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数。用符号 C(n,m) 表示。C(n,m)==A(n,m)/m!;C(n,m)=C(n,n-m)。(n>=m)

其他排列与组合公式 从 n 个元素中取出 m 个元素的循环排列数=A(n,m)/m=n!/m(n-m)!. n 个元素被分成 k 类,每类的个数分别是 n1,n2,…nk 这 n 个元素的全排列数为 n!/(n1!×n2!×…×nk!). k 类元素,每类的个数无限,从中取出 m 个元素的组合数为 C(m+k-1,m)。

容斥原理

设 A1,A2 为有限集合,其元素个数分别为|A1|,|A2|,则| A1∪A2|=| A1+A2|-| A1∩A2|
这个定理,常称作包含排斥原理,也就是容斥原理。

对于需要用到容斥原理的题型,一般都比较容易看出来用的方法,而且一般采用深搜的方法进行运算


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!