数论基础

bmatrix · 2022-01-09 11:24:43 · 个人记录

数论基础

基本概念：

模：a\bmod p 即 a\div p 的余数

整除：a\mid b 即 b\bmod a=0 ，同时称 a 是 b 的因数（约数）

质数：有且只有两个约数的数（ 1 不是质数，因为它只有一个约数）

质因数分解：将一个正整数 n 分解为 n=\prod_{i=1} p_i^{k_i}\;(p_i为质数,k_i\in\mathbb{N^*}) 的形式叫做质因数分解

同余：a\equiv b \pmod p 即 a\bmod p=b\bmod p

最大公约数：\gcd(a,b) ，顾名思义即 a 和 b 的公有的约数中最大的一个，无歧义时可记作 (a,b)

互质：a 与 b 互质即 \gcd(a,b)=1，记作 a\perp b

快速幂

目的：快速求出

考虑将 b 按二进制位分解：

其中 i 是非负整数， k_i\in \left \{ 0,1 \right \} ，是 b 每一二进制位上的值。

根据幂运算的性质 x^m x^n=x^{m+n} 则

因此我们只需要求出 a^{2^0},a^{2^1},a^{2^2}\dots ，就能在 O(\log b) 的复杂度内求出 a^b\bmod p 。

code:

typedef long long ll;
ll fast_pow(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

最大公约数

显然的性质：

• \gcd(a,0)=a
• \gcd(a,b)=\gcd(a-b,b)

由第二条性质可以推得：

其中 k 为整数，也就是

我们只需要一直模到 b=0 ，此时 \gcd(a,b) 就是 a 。

这就是著名的欧几里得算法（辗转相除法），复杂度 O(\log\max(a,b)) 。

code:

int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

扩展欧几里得算法

形如 ax\equiv c\pmod b 的同余方程叫做线性同余方程。显然，此方程与不定方程 ax+by=c 同解。

其中显然，当且仅当 \gcd(a,b)\mid c 时，方程有整数解。

扩展欧几里得算法就是求出 ax+by=\gcd(a,b) 的一组整数解。

如果我们还知道一组 x',y'，能使

由于 a\bmod b=a-b\times\left\lfloor\frac ab\right\rfloor：

因此当

时，方程一定有解。

那么这个过程就变成了一个递归的过程，每次递归下去都会由 a,b 变成 b,a\bmod b，容易发现，这和欧几里得算法的过程是一样的，最后一定会有 a=\gcd(a,b),b=0 的时刻，这就是递归出口。

方程 \gcd(a,b)x+0\times y=\gcd(a,b) 的整数解一定是 x=1,y\in\mathbb{Z} ，建议 y 取 0。

code：

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
}

最后对答案做一些处理，令 x=(x\bmod b+b)\bmod b，就一定能得到最小整数解。

注意：利用扩展欧几里得求解时，参数不能为无符号，因为可能存在负数！

质数筛

埃氏筛

如果一个数是质数，它的所有不是自己的倍数都不是质数，因此将这些数标记不是质数。

而如果一个数不是任何小于它且不是 1 的数的倍数，这个数一定是质数。

code：

bool not_prime[N];//标记数组
void init(){
    not_prime[1]=1;
    for(int i=2;i<=n;i++){
        if(not_prime[i])continue;
        for(int j=2;i*j<=n;j++)
            not_prime[i*j]=1;//标记质数的所有倍数
    }
}

时间复杂度 O(n\log\log n) （我不会证明）。虽然 \log\log n 很小，但是在数据极大的时候还是可以被卡掉（洛谷线性筛模板）。

欧拉筛（线性筛）

埃氏筛的复杂度里带一个 \log\log ，就是因为对于同一个合数，可能会被标记多次。

欧拉筛可以避免这个问题，其目标是令每个合数只被其最小质因子标记一次。

code：

bool not_prime[N];//标记数组
int prime[N];//记录已经筛出来的质数
void init(){
    not_prime[1]=1;
    for(int i=2;i<=n;i++){
        if(!not_prime[i])prime[++tot]=i;
        for(int j=1;j<=tot;j++){//遍历已经筛出来的质数
            if(i*prime[j]>n)break;
            not_prime[i*prime[j]]=1;
            if(i%prime[j]==0)break;//精髓
        }
    }
}

由于我太菜不会讲，正确性及原理详情出门左转洛谷线性筛模板题解区。

复杂度 O(n) 。

此外，可以通过线性筛预处理每个数的最小质因数，进行高效的质因数分解。

费马小定理

欧拉函数

欧拉函数定义为小于等于 n 的所有整数中与 n 互质的个数，记作 \varphi(n)。\forall n\in\mathbb N^*，有：

特别地，\varphi(1)=1。

对于这个式子，可以用容斥原理证明。
证明过程中最后那个因式分解可以用数学归纳法验证。

有了这个式子，则性质显然：

1. 若 n 为质数，则 \varphi(n)=n-1
2. 若 m\perp n，\varphi(mn)=\varphi(m)\varphi(n)
3. 若 m|n，\varphi(mn)=m\varphi(n)

因此，每个数的欧拉函数值可以用线性筛求出来：

bool not_prime[N];
int prime[N],phi[N];
void init(){
    vis[1]=1;phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            prime[tot++]=i;
            phi[i]=i-1;
            vis[i]=1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

欧拉定理

证明：

对于整数 p，令 S=\{x\in\mathbb N^*\mid x\perp p\}，则显然 |S|=\varphi(n)。

对于一个整数 a，使 a\perp p，我们证明以下两命题：

1. \forall x\in S,ax\perp p
2. \forall x_i\in S,x_j\in S,且x_i\neq x_j,有ax_i\not\equiv ax_j\pmod p

第一条显然。a,x 均和 p 没有相同因数，相乘后也一定没有相同因数。

对于第二条可利用反证法：若 ax_i\equiv ax_j\pmod p，则 x_i\equiv x_j\pmod p，与定义矛盾。因此 ax_i\not\equiv ax_j\pmod p。

二者结合可知：如果令 S'=\{y\in\mathbb N^*\mid y=ax\bmod p,x\in S\}，则一定有 S=S'。

因此：

即：

提取 a：

约简可得：

容易看出费马小定理就是欧拉定理在 p 为质数时的一种特殊情况。