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

符号与约定

非特殊声明下，本文所涉及的数均为非负整数。
$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$，都可以表示为有限个素数之积。即可以表示为：

这也是标准素因数分解式。
根据这个式子，设 $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)=\gcd(b,a\bmod b)$。递归执行，边界为 $\gcd(a,0)=a$。时间复杂度 $O(\log \min(a,b))$。

裴蜀定理

对于 $a,b$，存在 $x,y$ 使得

并且方程 $ax+by=c$ 有解当且仅当 $\gcd(a,b)\mid c$。以下是求解过程的推导：

像欧几里得算法一样递归求解即可。这个算法叫做扩展欧几里得算法。

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$ 互素的数的个数。

证明：容斥，但我不会。
欧拉定理：
若 $a,m$ 互质，则 $a^{\varphi(m)}\equiv 1\pmod m$。
扩展欧拉定理：

都不会证。

线性同余方程组

扩展中国剩余定理

又称 exCRT。
给定同余方程组

在模数不保证互质的情况下求解 $x$。
原理：exCRT 的本质是合并线性同余方程。
定理：若方程组有解，则解在模 $\operatorname{lcm}(m_1,m_2,\cdots,m_n)$ 意义下唯一，否则无解。
求解过程：
考虑 $2$ 个同余方程的情况：

设 $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}$，则方程变为：

因为 $\gcd(m_1’,m_2’)=1$，所以可以直接用扩展欧几里得算法求出 $k_1$ 的一个特解 $k_1^$。$k_1$ 的通解为 $k_1=k_1^+t\times m_2’$，代回，得到 $x$ 的通解为

注意到 $m_1m_2’=\dfrac{m_1m_2}{d}=\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