数论知识点总结
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=a−kb,根据同余关系可得:r%gcd(a,b)=0,因此gcd(a,b)=gcd(b,a%b)
code:
1 | int gcd(int a,int b){ |
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=a−a/b∗b
因而ax1+by1=bx2+ay2−a/b∗by2=ay2+b∗(x2−a/b∗y2)
那么我们就得到了一组合法的x1,y1的解:
x1=y2,y1=x2−a/b∗y2
也就是我们递归下去即可。当b=0的时候我们就可以发现x=1,y=0是合法的
这是我们再返回x=1,y=0。最后就一直会回溯下去,得到我们的x1,y1
1 | void exgcd(int a,int b){ |
但是如果要求ax+by=gcd(a,b)的最小整数解的时候,我们就要对x批量的加上b的倍数,但是这不会影响最终的结果。
因为ax+by+kab−kab=a(x+kb)+b∗(y−ka),这样依旧是合法的。
因此我们直接让x=(x%b+b)%b即为最终的答案。
3.逆元
对于a和m,如果ax≡1(modm),那么称x是a在m下的逆元。
那么我们该怎么求解逆元呢?我们将逆元的等式转化一下:
ax+my=1
由于ax+my=k有解当且仅当k%gcd(a,m)=0的时候有解,说明gcd(a,m)=1
那么我们直接用扩展欧几里得求解即可。
1 | int x,y; |
逆元一般是用在除法取模上面,如(a/b)%m即为a%m∗inv(b,m)
4.埃拉托斯特尼筛法
埃拉托斯特尼筛法是一个复杂度为nlnnlnn的筛法。
当选中一个数为素数的时候,就把以这个数为因子的数全部筛掉即可。
1 | const int N=1e6+100; |
5.费马小定理
假设a是一个整数,p是一个质数,那么ap−a是p的倍数
即ap≡a(modp),如果a不是p的倍数,这个定理也可以写成:
ap−1≡1(modp)
6.线性同余方程求解
形如ax≡b(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(1−1p1)(1−1p2)…(1−1pn)
其中p1,p2,…pn为x的质因数。