算法之数论-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法之数论。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数论

1.快速幂算法

原理

计算a的b次幂，我们首先会想到的是用一个循环，每次乘以一个a，乘b次，这种情况下所需的时间复杂度为O(b)。而快速幂算法则是利用倍增思想进行迭代求解，可以将时间复杂度降低到O(logb)。

分为两种情况：

当b为偶数时：
$a^b=a^{\frac{b}{2}}\times a^{\frac{b}{2}}=({a^2})^{\frac{b}{2}}$
当b为奇数时：

$a^b=a\times a^{\frac{b}{2}}\times a^{\frac{b}{2}}=a\times ({a^2})^{\frac{b}{2}}（这里的\frac{b}{2}向下取整）$

代码实现

public static long qmi(long a, long b, long mod) {
        long res = 1;
        while (b > 0) {
            //判断b是否为奇数
            if ((b & 1) == 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;// b/=2
        }
        return res;
    }

2.模运算

基本概念

取模：我们把a除以b所得的余数记为 a mod b
整除:若x可以被y整除，则记为y|x,如：4|12、3|6;
最大公约数： GCD(Greatest Common Divis)
最小公倍数：LCM(Least Common Multiple)

gcd(x,y)可以通过辗转相除法得到

lcm(x,y)可以通过下面公式得到：
$lcm(x,y)=\frac {x \times y} {gcd(x,y)}$

1.基本规则

$(a+b)\%p=(a\%p+b\%p)\%p\\ (a-b)\%p=(a\%p-b\%p)\%p\\ (a\times b)\%p=(a\%p\times b\%p)\%p\\ (a^b)\%p=((a\%p)^b)\%p$

2.同余式

若存在a mod m=b mod m，即a除以m与b除以m的余数相等，则记为：
$a\equiv b(mod \quad p)$

基本性质

若存在：
$a\equiv b(mod\quad m) 且b\equiv d(mod\quad m)$
则有：
$\equiv b+d(mod \quad m)\\ a-c \equiv b-d(mod \quad m)\\ a\times c \equiv b\times d(mod \quad m)$

如果答案对一个数取模，那么先取模再加、乘都是不影响最终答案的。

注意：除法没有这些性质。

3.剩余系

是指对于某一个特定的整数的n，一个整数集合中的数模n所得的余数域。如果一个剩余系中包含了这个正整数所有可能的余数（一般来说，对于正整数n，最多有n个余数：0，1，2，…，n-1）,则称剩余系是模n的一个完全剩余系。记作：
$Z_n$

完全剩余系里的每一个元素代表了所有模n意义下与它同余的整数。例如n=5时，5的完全剩余系中的3实际上代表了3，8，13，18这些模5余3的数。在完全剩余系中的加法、减法、乘法全部都是在模n的意义下的，例如：在5的完全剩余系中，3+2=0，3*2=1。

4.逆元

在实数运算中，除以一个数就等于乘以这个数的倒数，如果ab=1，则说明a与b互为倒数。在模运算中也有类似的概念，即逆元。

如果在n的完全剩余系中存在两个元素a，b满足ab=1，那么我们救说a，b互为模n意义下乘法的逆，记作：
$a=b^{-1},b=a^{-1}$
例如：在15的完全剩余系中，7*13=1，那么我们就说a，b互为模n意义下的逆元。

我们知道，除以一个数等于乘以这个数的倒数，在模运算中，若一个数存在逆元，那么除以一个数等于乘以这个数的逆元。例如，在5的完全剩余系中，
$4\div3=4\times3^{-1}=4\times2=3$

5.除法求模

小费马定理

若p为质数，且gcd(a,p)=1，则有
$a^{p-1}\equiv 1(mod\quad p)\\ a^{p-2}\equiv \frac {1}{a} (mod\quad p)$
转化后：
$\frac {b}{a} \equiv b\times a^{p-2}(mod\quad p)$
此时，我们就将除法求模问题转换为了乘法求模问题。文章来源地址https://www.toymoban.com/news/detail-831394.html