Loading [MathJax]/jax/output/HTML-CSS/jax.js

数论知识点总结

数论知识点总结

1.gcd(最大公约数)

对于给出的两个数a,b,我们可以用欧几里得算法来计算最大公约数。欧几里得算法的精髓就在于下面这个公式:
gcd(a,b)=gcd(b,a%b)

证明:
已知:gcd(a,b)|a并且gcd(a,b)|b,设a%b=r,则a=r+kb,故r=akb,根据同余关系可得:r%gcd(a,b)=0,因此gcd(a,b)=gcd(b,a%b)

code:

1
2
3
int gcd(int a,int b){
return b?gcd(b,a%b):a
}

2.exgcd(扩展欧几里得算法)

扩展欧几里得算法是用于求解ax+by=gcd(a,b)的一组解的算法。
根据欧几里得算法我们可知:gcd(a,b)=gcd(b,a%b)
我们假设x1,y1是满足条件的一组解

那么ax1+by1=gcd(a,b)

gcd(a,b)=gcd(b,a%b)

ax1+by1=bx2+a%by2

a%b=aa/bb

因而ax1+by1=bx2+ay2a/bby2=ay2+b(x2a/by2)

那么我们就得到了一组合法的x1,y1的解:

x1=y2,y1=x2a/by2

也就是我们递归下去即可。当b=0的时候我们就可以发现x=1,y=0是合法的

这是我们再返回x=1,y=0。最后就一直会回溯下去,得到我们的x1,y1

1
2
3
4
5
6
7
8
9
void exgcd(int a,int b){
if(!b){
x=1,y=0;
return ;
}
exgcd(b,a%b)
int temp=x;
x=y;y=temp-a/b*x;
}

但是如果要求ax+by=gcd(a,b)的最小整数解的时候,我们就要对x批量的加上b的倍数,但是这不会影响最终的结果。

因为ax+by+kabkab=a(x+kb)+b(yka),这样依旧是合法的。

因此我们直接让x=(x%b+b)%b即为最终的答案。

3.逆元

对于am,如果ax1(modm),那么称xam下的逆元。

那么我们该怎么求解逆元呢?我们将逆元的等式转化一下:
ax+my=1

由于ax+my=k有解当且仅当k%gcd(a,m)=0的时候有解,说明gcd(a,m)=1

那么我们直接用扩展欧几里得求解即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int x,y;
void exgcd(int a,int b){
if(!b){
x=1,y=0;
return ;
}
exgcd(b,a%b)
int temp=x;
x=y;y=temp-a/b*x;
}
int inv(int a,int m){//a在m下的逆元
exgcd(a,m);
return (x%m+m)%m;
}

逆元一般是用在除法取模上面,如(a/b)%m即为a%minv(b,m)

4.埃拉托斯特尼筛法

埃拉托斯特尼筛法是一个复杂度为nlnnlnn的筛法。
当选中一个数为素数的时候,就把以这个数为因子的数全部筛掉即可。

1
2
3
4
5
6
7
8
9
10
11
12
const int N=1e6+100;
vector<int> pr;
bool vis[N];
void seive(){
vis[0]=vis[1]=1;
for(int i=2;i<=N-10;i++){
if(!vis[i]){
pr.push_back(i);
for(int j=2*i;j<=N-10;j+=i) vis[j]=1;
}
}
}

5.费马小定理

假设a是一个整数,p是一个质数,那么apap的倍数

apa(modp),如果a不是p的倍数,这个定理也可以写成:

ap11(modp)

6.线性同余方程求解

形如axb(modm)即为线性同余方程。
将线性同余方程变形后即可得到:

ax+my=b
只有当b%gcd(a,m)=0时该方程才有解。
我们先利用扩展欧几里得算法求出

ax+my=gcd(a,m)的一组解(x0,y0),那么x=x0(b/gcd(a,m))%m
即为原方程的一组解。

7.欧拉函数

欧拉函数即为小于n的数中与n互质的数的个数
比如φ(8)=4
欧拉函数的通式为:

φ(x)=x(11p1)(11p2)(11pn)

其中p1,p2,pnx的质因数。