之前写几篇数论文章已经忘了，而且写的也不是很美丽，正巧今天讲课讲了一遍数论，那就当从头复习一遍。

符号与约定

非特殊声明下，本文所涉及的数均为非负整数。
\(a\mid b\) 表示 \(b\) 是 \(a\) 的倍数，\(a\) 是 \(b\) 的约数。
\(\gcd(a,b)\) 表示 \(a\) 和 \(b\) 的最大公约数。在不引起混淆的前提下可记作 \((a,b)\)。
\(\operatorname{lcm}(a,b)\) 表示 \(a\) 和 \(b\) 的最小公倍数。在不引起混淆的前提下可记作 \([a,b]\)。

素数

数量估计：小于等于 \(x\) 的素数约有 \(\dfrac{x}{\ln x}\) 个。

埃拉托斯特尼筛法

原理：所有合数必然都有素因子，则我们可以采用“标记”的思想，若遇到一个未被标记的数，则其必为素数，并将它的所有倍数标记。反之它就是合数。时间复杂度 \(O(n\log \log n)\)。我不会证。简单的优化是标记数组使用 std::bitset，性能甚至超越了 \(O(n)\) 的线性筛法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bitset>
using namespace std;
constexpr int N=1e7+10;
int n;
bitset<N> p;
int main(){
    n=1e7;
    p.set();
    p[0]=p[1]=0;
    for(int i=2;i<=n/i;i++)
        if(p[i])
            for(int j=i*i;j<=n;j+=i)
                p[j]=0;
    return 0;
}
外层循环只需执行到 \(\sqrt{n}\) 即可。使用安全的除法运算防止 int 溢出。

线性筛法

也叫欧拉筛法。其时间复杂度为线性的原因是每个合数仅会被标记 \(1\) 次。更为重要的是，在筛出所有质数的同时也能求出所有数的最小质因子，可以优化质因数分解。 

1
2
3
4
5
6
7
8
9
10
11
constexpr int N=1e7+10,M=7e5+10;
int n,p[M],e[N],tot;//e[i]存储i的最小质因子在p[]中的下标
int main(){
    n=1e7;
    for(int i=2;i<=n;i++){
        if(!e[i]) p[e[i]=++tot]=i;
        for(int j=1;j<=e[i]&&p[j]<=n/i;j++)
            e[p[j]*i]=j;
    }
    return 0;
}

算术基本定理

任何一个数 \(n\)，都可以表示为有限个素数之积。即可以表示为： \[n=\prod p_i^{\alpha_i}\] 这也是标准素因数分解式。
根据这个式子，设 \(a=\prod p_i^{\alpha_i}\)，\(b=\prod p_i^{\beta_i}\)，则 \(\gcd(a,b)\) 可表示为 \(\prod p_i^{\min(\alpha_i,\beta_i)}\)，\(\operatorname{lcm}(a,b)\) 可表示为 \(\prod p_i^{\max(\alpha_i,\beta_i)}\)。根据这个定义，容易证明 \[\gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b\]

同余

求最大公约数

辗转相除法，又名欧几里得算法。原理：\(\gcd(a,b)=\gcd(b,a\bmod b)\)。递归执行，边界为 \(\gcd(a,0)=a\)。时间复杂度 \(O(\log \min(a,b))\)。

裴蜀定理

对于 \(a,b\)，存在 \(x,y\) 使得
\[ax+by=\gcd(a,b)\] 并且方程 \(ax+by=c\) 有解当且仅当 \(\gcd(a,b)\mid c\)。以下是求解过程的推导：
\[\begin{aligned} ax+by&=\gcd(a,b)\\ &=\gcd(b,a\bmod b)\\ &=bx'+(a-b\times \lfloor\frac{a}{b}\rfloor)y'\\ &=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y') \end{aligned}\] 像欧几里得算法一样递归求解即可。这个算法叫做扩展欧几里得算法。

1
2
3
4
5
6
7
8
9
10
11
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 temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}

逆元

线性求法：
要求模数 \(p\) 为质数。显然在 \(i=1\) 时 \(i^{-1}=1\)，考虑 \(i>1\) 的情况。设 \(k=\lfloor\dfrac{p}{i}\rfloor,j=p\bmod i\)，则 \(p=ki+j\)。则 \(ki+j\equiv 0 \pmod p\)，两边同时乘 \(i^{-1}j^{-1}\)，得 \(kj^{-1}+i^{-1}\equiv 0\pmod p\)，移项并回代 \(k,j\)，得 \(i^{-1}\equiv -\lfloor\dfrac{p}{i}\rfloor\times(p\bmod i)^{-1} \pmod p\) 实际操作中为了避免负数，可以将 \(-\lfloor\dfrac{p}{i}\rfloor\) 替换为 \(p-\lfloor\dfrac{p}{i}\rfloor\)。 

1
2
3
inv[1]=1;
for(int i=2;i<=n;i++)
    inv[i]=(long long)(p-p/i)*inv[p%i]%p;
不过一般都直接用费马小定理快速幂求出。

欧拉函数

定义欧拉函数 \(\varphi(n)\) 为 \(1\sim n\) 中与 \(n\) 互素的数的个数。
\[\varphi(n)=n\prod \frac{p_i-1}{p_i}\] 证明：容斥，但我不会。
欧拉定理：
若 \(a,m\) 互质，则 \(a^{\varphi(m)}\equiv 1\pmod m\)。
扩展欧拉定理： \[a^b\equiv \begin{cases}a^{b\bmod \varphi(m)},&\gcd(a,m)=1,\\ a^b,&\gcd(a,m)\ne 1,b<\varphi(m),\\ a^{(b\bmod\varphi(m))+\varphi(m)},&\gcd(a,m)\ne 1,b\ge\varphi(m). \end{cases} \pmod m \] 都不会证。

线性同余方程组

扩展中国剩余定理

又称 exCRT。
给定同余方程组
\[\begin{cases} x\equiv a_1\pmod {m_1},\\ x\equiv a_2\pmod {m_2},\\ \cdots\\ x\equiv a_n\pmod {m_n}. \end{cases}\] 在模数不保证互质的情况下求解 \(x\)。
原理：exCRT 的本质是合并线性同余方程。
定理：若方程组有解，则解在模 \(\operatorname{lcm}(m_1,m_2,\cdots,m_n)\) 意义下唯一，否则无解。
求解过程：
考虑 \(2\) 个同余方程的情况： \[\begin{cases} x\equiv a_1\pmod {m_1},\\ x\equiv a_2\pmod {m_2}. \end{cases}\] 设 \(x=k_1m_1+a_1=k_2m_2+a_2\)，则 \(k_1m_1-k_2m_2=a_2-a_1\)。注意：根据裴蜀定理，当且仅当 \(\gcd(m_1,m_2)\mid (a_2-a_1)\) 时此方程有解。设 \(d=\gcd(m_1,m_2)\)，原式写为 \(\dfrac{m_1}{d}k_1-\dfrac{m_2}{d}k_2=\dfrac{a_2-a_1}{d}\)，设 \(m_1'=\dfrac{m_1}{d},m_2'=\dfrac{m_2}{d},c=\dfrac{a_2-a_1}{d}\)，则方程变为：
\[m_1'k_1+m_2'k_2=c\] 因为 \(\gcd(m_1',m_2')=1\)，所以可以直接用扩展欧几里得算法求出 \(k_1\) 的一个特解 \(k_1^*\)。\(k_1\) 的通解为 \(k_1=k_1^*+t\times m_2'\)，代回，得到 \(x\) 的通解为
\[\begin{aligned} x&=k_1m_1+a_1\\ &=(k_1^*+t\times m_2')m_1+a_1\\ &=m_1k_1^*+a_1+t\times m_1m_2' \end{aligned}\] 注意到 \(m_1m_2'=\dfrac{m_1m_2}{d}=\operatorname{lcm}(m_1,m_2)\)，所以有
\[x\equiv m_1k_1^*+a_1\pmod{\operatorname{lcm}(m_1,m_2)}\] 至此，我们成功合并了两个方程。
对于 \(n\) 个方程的合并，只需重复以上步骤，一直合并到只剩一个方程 \(x\equiv A\pmod M\)，其中 \(M=\operatorname{lcm}(m_1,m_2,\cdots,m_n)\)。时间复杂度 \(O(n\log M)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int exCRT(){
    int a1=a[1],m1=m[1];
    for(int i=2;i<=n;i++){
        int a2=a[i],m2=m[i];
        int k1,k2;
        int d=exgcd(m1,m2,k1,k2);
        if((a2-a1)%d!=0)
            return -1;
        k1*=(a2-a1)/d;
        int t=m2/d;
        k1=(k1%t+t)%t;
        a1+=k1*m1;
        m1=m1/d*m2;
        a1=(a1%m1+m1)%m1;
    }
    return a1;
}

其他

附表：

参考资料：
https://oi-wiki.org/math/ https://www.cnblogs.com/Tmbcan/p/18903233