<总结>基本数论算法

2020年1月5日 0条评论 389次阅读 0人点赞 oldcat

本文来自原博客，最后一次更新时间为2019年7月，请知悉

基本数论算法

快速幂

放在这里，防止大佬突然大脑短路
1. 非递归
原来觉得这种方法很难，现在却是随手打出来了。不得不感叹下时光的力量啊

long long power(int a, int n, int k){
    long long ans = 1;
    long long base = a;//base保存a的二次幂的幂
    while(n){
        if(n & 1){
            ans *= base;//最低位为1，将base计入答案
            ans %= k;
        }
        base *= base;
        base %= k;
        n >>= 1;
    }
    return ans%k;
}

递归

long long slove(int p){
    if(p == 1){
        return b;
    }
    if(p == 0){
        return 1;
    }
    long long  ans = slove(p/2);
    ans *= ans;
    ans %= k;
    if(p & 1){
        ans *= b;
        ans %= k;
    }
    return ans;
}

最大公约数GCD、最小公倍数LCM

辗转相除

$\gcd(a, b) = \gcd(b, a\bmod b)$

$\text{设}d=\gcd(a,b)\\ \Rightarrow a=pd,b=qd\\ \therefore a\bmod b=(p\bmod q)\times d,p\bmod q = 1\\ \therefore \gcd(p, q) = \gcd(q, p\bmod q) = 1\\ \therefore \gcd(p, q)\times d = \gcd(q, p\bmod q)\times d\\ \Rightarrow \gcd(a, b) = \gcd(b, (p\bmod q)\times d)\\ = \gcd(b, a\bmod b)$

$lcm(a, b) = \cfrac{a\times b}{\gcd(a, b)}$

什么？你只满足于辗转相除？
辗转相除取模不要时间？

更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

~~语文奥赛~~
1. 任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
2. 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
3. 第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

通常认为，算法描述中的第一步“可半者半之”是指分子分母皆为偶数的时候，首先用2约简。因为更相减损术原先是专用来约分，所以并不用考虑最后计算结果时，要把第一步中约掉的若干个2再乘回去。加入这一步的原因可能是分母、分子皆为偶数在分数加减运算中比较容易遇到，用这种方法有可能减少数字的位数，简化计算。
当然，省略这个以2约简的步骤，也能得到正确的答案。

int gcd(int a, int b){
    if(a == b) return a;
    if(a < b)
        return gcd(b, a-b);
    else
        return gcd(a, b-a);
}

更相减损术避免了大整数取模的性能问题，但是其依靠两数求差的方式来递归，运算次数大于辗转相除法。

用更相减损术优化的方法

当 $a$ 和 $b$ 均为偶数， $\gcd(a,b) = 2\times\gcd(a/2, b/2)$
当 $a$ 为偶数， $b$ 为奇数， $\gcd(a,b) = \gcd(a/2, b)$
当 $a$ 为奇数， $b$ 为偶数， $\gcd(a,b) = \gcd(a, b/2)$
当 $a$ 和 $b$ 均为奇数，利用更相减损术运算一次， $\gcd(a,b) = \gcd(b, a-b)$ ， $a-b$ 必定为偶数

算法效率稳定 $\log_2\max(a, b)$ ，且除2可用移位运算，常数小
递归版本：

long long gcd(long long a, long long b){
    if(a == b)
        return a;
    if(a == 0 || b == 0)
        return a+b;
    if((a&1)==0 && (b&1)==0)
        return gcd(a>>1, b>>1)<<1;
    if((a&1) && (b&1)){
        if(a>b)
            return gcd(b, a-b);
        else
            return gcd(a, b-a);
    }
    if(a&1)
        return gcd(a, b>>1);
    return gcd(a>>1, b);
}

非递归版本：

long long gcd(long long a, long long b){
    long long ans = 1;
    while(true){
        if(a == b){
            ans *= a;
            return ans;
        }
        if(a == 0 || b == 0){
            ans *= a+b;
            return ans;
        }
        if(a & 1){
            if(b & 1){
                long long c;
                if(a > b){
                    c = b;
                    b = a-b;
                    a = c;
                }else{
                    c = a;
                    a = b-a;
                    b = c;
                }
            }else{
                b >>= 1;
            }
        }else{
            if(b & 1){
                a >>= 1;
            }else{
                a >>= 1;
                b >>= 1;
                ans <<= 1;
            }
        }
    }

同余

定义

两个整数 $a$ , $b$ ,若它们除以整数 $m$ 所得的余数相等,则称 $a$ 与 $b$ 对于模 $m$ 同余或 $a$ 同余于 $b$ 模 $m$ ,记做 $a\equiv b\pmod m$ ,例如 $26\equiv2\pmod{12}$
显然,有如下事实
1. 若 $a\equiv0\pmod m$ ，则 $m|a$ ；
2. $a\equiv b\pmod m$ 等价于 $a$ 与 $b$ 分别用 $m$ 去除，余数相同。

公式

反身性： $a\equiv a\pmod m$ ；
对称性：若 $a\equiv b\pmod m$ ，则 $b\equiv a\pmod m$ ；
传递性：若 $a\equiv b\pmod m$ ， $b\equiv c\pmod m$ ，则 $a\equiv c\pmod m$ ；
同余式相加：若 $a\equiv b\pmod m$ ， $c\equiv d\pmod m$ ，则 $a\pm c\equiv b\pm d\pmod m$ ；
同余式相乘：若 $a\equiv b\pmod m$ ， $c\equiv d\pmod m$ ，则 $ac\equiv bd\pmod m$ 。

逆元

定义

若 $ax\equiv 1 \pmod p$ ,则 $x$ 为 $a$ 关于 $p$ 的逆元--乘法代替除法

求法

费马小定理
对于质数 $p$ ，任意整数 $a$ ，均满足： $a^p\equiv a\pmod p$ .当 $a$ 与 $p$ 互质， $a^{p-1}\equiv 1\pmod p$ .所以 $a^{p-2}$ 是 $a$ 的逆元
欧拉定理
拓展欧几里得算法
线性时间推范围的所有逆元

$\begin{aligned} &\because &P\bmod a &=P-\lfloor\cfrac P a\rfloor\times a\\ &\therefore &P\bmod a &\equiv -\lfloor\cfrac P a\rfloor\times a\pmod P\\ &\therefore &1 &\equiv -\lfloor\cfrac P a\rfloor\times a \times(P\bmod a)^{-1}\pmod P\\ &\therefore &a^{-1} &\equiv -\lfloor\cfrac P a\rfloor\times (P\bmod a)^{-1}\pmod P\\ &\end{aligned}$

#include<cstdio>

int inv[N];

int main(void){
    inv[1] = 1;
    for(int i = 2; i < N; ++ i){
        inv[i] = (P - P/i) * inv[P % i] % P;
    }
}

排列组合

排列的定义:从 $n$ 个不同元素中，任取 $m(m≤n,m,n\in N^\star）$ (下同)个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列
从 $n$ 个不同元素中取出 $m$ 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $A(n,m)/A_n^m$ 表示。

组合的定义：从 $n$ 个不同元素中，任取 $m$ 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数。用符号 $C(n,m)/C_n^m/\binom{n}{m}$ 表示。

计算

公式

$A_n^m = n(n-1)\cdots(n-m+1)=\cfrac{n!}{(n-m)!}\\ C_n^m = \cfrac{A_n^m}{m!}=\cfrac{n!}{m!(n-m)!}$

递推

$C_n^m = C_{n-1}^m+C_{n-1}^{m-1} A_n^m = A_{n-1}^m+A_{n-1}^{m-1}\cdot m$

卢卡斯定理（求C(n, m) mod p）

$C(n, m)=C(n\bmod p,m\bmod p)C(m/p, n/p)$
醒醒，p要是质数！！！！！！！！！！

组合数性质

$\sum_{i=0}^{n}C_n^i = 2^n$
$\sum_{i=0}^{n}(-1)^i\cdot C_n^i = 0$
$C_n^m = C_n^{n-m}$
$C_{n+m}^r = \sum_{i=0}^rC_n^i+C_m^{r-i}$

二项式定理

$(a+b)^n = C_n^0 x^ny^0+C_n^1 x^{n-1}y^1+\cdots+C_n^{n-1} x^1y^{n-1}+C_n^n x^0y^n$

容斥原理

$|A_1\cup A_2\cup A_3\cup\cdots\cup A_n|\\ =\sum_{1\le i\le n}|A_i|\\ -\sum_{1\le i< j\le n}|A_i\cap A_j|\\ +\sum_{1\le i< j< k\le n}|A_i\cap A_j\cap A_k|\\ -\cdots\\ +(-1)^{m-1}|A_1\cap A_2\cap\cdots\cap A_n|$

卡特兰Catalan数Cn

Catalan数

第一类Stirling数（？）

第一类Stirling数表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目。
递推式 $s(n,m)=s(n-1,m-1)+s(n-1,m)\cdot(n-1)\quad1\le m\le n-1$
边界：
$\begin{cases} s(p,0)=0 ,p\ge 1 \\ s(p,p)=1 ,p\ge 0 \end{cases}$

第二类Stirling数（？）

第二类Stirling数实际上是集合的一个拆分，表示将 $n$ 个不同的元素拆分成 $m$ 个集合的方案数
递推式 $S(n,m)=S(n-1,m-1)+S(n-1,m)\cdot m\quad1\le m\le n-1$
边界： $\begin{cases}S(p,p)=1 ,p\ge 0 \\ S(p,0)=0 ,p\ge 1\end{cases}$

贝尔数（？）

贝尔数给出了集合划分的数目, $B_n$ 是基数为 $n$ 的集合划分数目
(集合 $S$ 的一个划分是定义为 $S$ 的两两不相交的非空子集的族，它们的并是 $S$ )
考虑这个集合最后一个数所在的集合，我们也可以得出他的一个递推公式
$B_{n+1} = \sum_{k=0}^nC_n^kB_k$

拓展欧几里得算法

裴蜀定理

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理
裴蜀定理得名于法国数学家艾蒂安·裴蜀。
裴蜀定理说明了对任何整数 $a,b$ 和它们的最大公约数 $d$ 关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式）。
丢番图方程（Diophantine Equation）：有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。最后这个限制使得丢番图方程求解与实数范围方程求解有根本的不同。丢番图方程又名不定方程、整系数多项式方程，是变量仅容许是整数的多项式等式；

若 $a,b$ 是整数,且 $\gcd(a,b)=d$ ，那么对于任意的整数 $x,y$ , $ax+by$ 都一定是 $d$ 的倍数，特别地，一定存在整数 $x,y$ ，使 $ax+by=d$ 成立。
证明:(转载：原博客链接)
1. 当 $b=0$ 时， $\gcd(a,b)=a$ ，此时 $x=1 , y=0$
2. 当 $b {\not=} 0$ 时
$\begin{aligned}\text{设}ax_1+by_1&=\gcd(a,b)\\ &=\gcd(b,a\bmod b)\\ &=bx_2+(a\bmod b)y_2\end{aligned}$
$\begin{aligned} &\because &a\bmod b&=a-\lfloor \cfrac a b\rfloor\times b\underline{\not=0}_{?}\\ &\therefore &ax_1+by_1&=bx_2+(a-\lfloor \cfrac a b\rfloor\times b)\times y_2\\ &\Rightarrow &ax_1+by_1&=bx_2+ay_2-\lfloor \cfrac a b\rfloor\times b\times y_2\\ &\Rightarrow &ax_1+by_1&=ay_2+bx_2-b\times \lfloor \cfrac a b\rfloor\times y_2\\ &\Rightarrow &ax_1+by_1&=ay_2+b(x_2-\lfloor \cfrac a b\rfloor\times y_2)\\ &\Rightarrow&&\begin{cases} x_1&=y_2 \\ y_1&=x_2-\lfloor \cfrac a b\rfloor\times y_2 \end{cases}\end{aligned}$
因为当 $b=0$ 时存在 $x , y$ 为最后一组解， $\gcd(a,b)=a$ ，此时 $x=1 , y=0$
而每一组的解可根据后一组得到
所以第一组的解 $x , y$ 必然存在,得证

扩展欧几里得算法ExGCD

根据上面的递推过程，我们可以在递归计算 $\gcd$ 的过程中顺便传两个实参（引用传递）来计算 $x_1, y_1$

int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;//普通gcd
    }
    int ret = exgcd(b, a%b, x, y);//普通gcd的返回值
                                //当然调用的过程已经算好了x2, y2
    int t = y;
    y = x - (a/b) * y;
    x = t;
    return ret;
}

ExGCD求逆元

求 $a$ 的逆元相当于找出满足满足 $ax-1=Py$ 的最小 $x$ ，（ $y$ 为未知数）
移项可得： $ax-Py=1$ ，我们用ExGCD解出一组 $x,y$ 就可以了
其实从这里也可以看出 $a$ 在模 $P$ 意义下有逆元当且仅当 $\gcd(a,P)=1$
板子：[洛谷1082]同余方程

质数

因数只有1和自己的数称为质数

常用结论

质数的个数是无限的（ $\approx \frac n {\ln n}$ ）

假若素数只有有限多个，设最大的一个是P，从2到P的全体素数是：
2,3,5,7,11,...,P
所有的素数都在这里，此外再没有别的素数了。
现在，我们来考察上面从2到P的全体素数相乘、再加上1这个数，设它是A，即
A=2×3×5×7×11×……×P+1
A是一个大于1的正整数，它不是素数，就是合数。
如果A是素数，那么，就得到了一个比素数P还要大的素数，这与素数P是最大素数的假设矛盾。
如果A是合数，那么，它一定能够被某个素数整除，设它能被g整除。
因为A被从2到P的任何一个素数除，余数都是1，就是都不能整除，而素数g是能整除A的，所以素数g不在从2到P的全体素数之中。这说明素数g是一个比素数P更大的素数，这又与P是最大的素数的假设矛盾。
上面的证明否定了素数只有有限多个的假定，这就证明了素数是无穷多个。
(算数基本定理)任何一个大于1的正整数，都可以唯一分解为有限个质数的乘积形式
算术基本定理可表述为：任何一个大于 $1$ 的自然数 $N$ ,如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积 $N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{a_n}$ ，这里 $P_1< P_2< P_3\cdots< P_n$ 均为质数，其中指数 $a_i$ 是正整数。这样的分解称为 $N$ 的标准分解式。最早证明是由欧几里得给出的，现代是由陈述证明。
若 $n$ 为质数，则 $\forall 1\le i$
(费马小定理)若 $p$ 是质数， $\gcd(a,p)=1$ ，则 $ap-1\equiv 1\pmod p$ （此定理可进一步推广为欧拉定理，其逆命题不成立）

筛素数

埃拉托色尼筛法

埃氏筛法是一种古老的筛选素数的方法，以古希腊数学家埃拉托色尼的名字命名
算法思想是从 $1\to n$ 中依次删除 $2$ 的倍数， $3$ 的倍数，...，从而得到所有的素数
第一层for本来是 $2\to n$ ，但是一个合数如果写成两个数相加，那么肯定一个数小于等于 $\sqrt n$
第二层for本来是从 $2$ 开始的，但是这里改成了 $i$ ,是因为如果有一个合数为 $i(i-k),0 < k < i,k\in N^\star$ ,那么这个数就会有一个更小的因子 $i-k$ ，在之前就会被筛掉
代码

const int n = 1000000;
bool a[n+1];
for(int i = 2; i <= sqrt(n); ++ i)
    if(a[i] == false)
        for(int j = i; i*j <= n; ++ j)
            a[j] = true;

但是这个方法每个合数都会被标记多次，而下面这个算法可以解决这个问题。

欧拉筛法

欧拉筛法和埃氏筛法思想差不多，但是欧拉筛法可以保证每个合数都是被它的最小的质因子筛去的
我们先回过头去看埃氏筛法哪里会重复标记质数：

2 => Yes ---  4,  6,  8, 10, 12
3 => Yes ---     *6,  9,    *12, 15
4 => No
5 => Yes ---            *10,        20

我们把12作为栗子：
$12=2\times6=3\times4$
所有按照欧式筛法，12会被2和3标记，我们可以想想办法让12只被其中一个标记。
根据算数基本定理，任何一个大于1的正整数，都可以唯一分解为有限个质数的乘积形式，如 $12=2\times2\times3$ 所以我们让第二层循环枚举2到n是十分浪费的，因为如果一个数能被一个合数整除，那么它也能被构成这个合数的质因子整除。
所以我们只需要将一个数用它的最小质因子筛去就可以了吧。
可是我们不知道一个数的最小质因子是多少，我们就又要对每个质数进行乘 $2$ ，乘 $3$ ，......又回到了最初的地方。
于是我们就多了个新的想法：用它和它的最小质因数的商去筛。
为什么我们会这样想呢？
我们未来降低无效访问的次数，却又要让每个合数都被访问到，那么我们就要确定唯一的一种访问方式，并且较好确定唯一性。最小质因数是不好确定唯一性的，但是一个数和它的最小质因数的商是可以比较好的判断的，只需要先确定一个数，然后用所有的质数去和它相乘就差不多了。
但是我们要这样做，就要先有一个质数表，但是我们的工作就是要求这个质数表。这就像你要精二斯卡蒂需要芯片组，但是得芯片组需要精二斯卡蒂，但是精二斯卡蒂就需要芯片组......
呃......其实你选中了一个数以后只需要把它和比他小的质数相乘，要不然那个乘出来的数的最小质因子就不是你乘的那个质数了（证明略），对吧。就像你打精二芯片只需要精一的干员一样
蛋但还有个问题，当我们选中了 $4$ 以后，比它小的质数有 $2, 3$ ，但是如果我们用 $4\times 3=12$ ，但 $12=2\times 6$ 。这是因为我们取的这个数是一个合数，它可以分解为一个质数和一个数相乘，当我们枚举的质数小于这个合数的最小质因数时，这样做是没问题的，但是如果我们枚举的质数3大于了这个合数4的最小质因数2以后，我们乘出来的这个数12的最小质因数2就不是我们乘的那个质数3了。这就是下面代码的//!!!的原因
所以我们拿个vector出来记录目前为止所有的质数就好了吧。
代码

vector<int> prime;
bool a[n];
for(int i = 2; i <= n; ++ i){
    if(a[i] == false)
        prime.push_back(i);
    for(int j = 0; j < prime.size() && i*j <= n; ++ j){//其实我更偏向用迭代器
        a[i*prime[j]] = true;
        if(i % prime[j] == 0)//!!!
            break;
    }
}

欧拉函数

在数论，对正整数 $n$ ，欧拉函数是小于 $n$ 的正整数中与 $n$ 互质的数的数目（特别地， $\varphi(1)=1$ ）。
若在算数基本定理中， $N=P_1^{a_1}P_2^{a_2}P_3^{a_3.}.....P_n^{a_n}$ ，则
$\varphi(N)=N\times\cfrac{p_1-1}{p_1}\times\cfrac{p_2-1}{p_2}\times\cdots\times\cfrac{p_n-1}{p_n}\\ =N\times\prod\limits_{\text{质数}p|N}(1-\frac 1 p)$
证明以后会补上的。咕咕咕

欧拉函数性质

$\forall n>1 ,1\to n$ 中互质的数的和为 $n\times \varphi(n)/2$
若 $a, b$ 互质，则 $\varphi(ab)=\varphi(a)\varphi(b)$
设 $p$ 为质数，若 $p|n$ 且 $p^2|n$ ，则 $\varphi(n)=\varphi(n/p)\times p$
设 $p$ 为质数，若 $p|n$ 但 $p^2\not|n$ ，则 $\varphi(n)=\varphi(n/p)\times (p-1)$
$\sum_{d|n}\varphi(d) = n$

积性函数

我快猝死了，积你太美（备注：这个人回头填坑打到这的时候文章字符数已经1.2w了）
积性函数：对于任意互质的整数 $a$ 和 $b$ 有性质 $f(ab)=f(a)f(b)$ 的数论函数。
完全积性函数：对于任意整数 $a$ 和 $b$ 有性质 $f(ab)=f(a)f(b)$ 的数论函数。
积性函数举例：
* $\varphi(n)$ －欧拉函数
* $\mu(n)$ －莫比乌斯函数
* $\gcd(n,k)$ －最大公因子( $k$ 固定)
* $d(n)$ － $n$ 的正因子数目
* $σ(n)$ － $n$ 的所有正因子之和
* $1(n)$ －不变的函数，定义为 $1(n) = 1$ （完全积性）
* $λ(n)$ －刘维尔函数，关于能整除 $n$ 的质因子的数目

积性函数性质：
用算术基本定理， $N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{a_n}$ ，那么积性函数 $f(n)=\prod_{i=1}^nf(p_i^{c_i})$

莫比乌斯函数

莫比乌斯函数基础

$\mathrm{M\ddot{o}bius}$
\mathrm{M\ddot{o}bius}
我们用 $\mu(n)$ 表示 $\mathrm{M\ddot{o}bius}$ 函数
$\mu(n) = \delta_{\omega(n)\Omega(n)}\lambda(n)$ ,在这里， $\lambda(n)$ 是刘维尔函数
喵喵喵？
好吧不皮了（到现在文章已经1w字符了）
莫比乌斯函数完整定义的通俗表达：
1. $dom\mu=\mathbb{N}$ ( $\mathrm{M\ddot{o}bius}$ 函数定义域为 $\mathbb N$ )
2. $\mu(n)=1$
3. 当 $n$ 存在平方因子时， $\mu(n)=0$
4. 当 $n$ 是素数或奇数个不同素数之积时， $\mu(n)=-1$
5. 当 $n$ 是偶数个不同素数之积时， $\mu(n)=1$

再人话一点
1. 当 $n$ 包含相同质因子时 $\mu(n)=0$
2. 当 $n$ 的质因子各不相同时
1. 当 $n$ 有偶数个质因子时 $\mu(n)=1$
2. 当 $n$ 有奇数个质因子时 $\mu(n)=-1$

好了你已经会基础的东西了接下来就靠你了：自我研究

喵呜