初等数论

a_blue_cell · 2022-09-01 20:35:42 · 算法·理论

1.2. 性质

1.2.1. 性质1

若 a\mid b,b\mid c ，则 a\mid c

证明：

1.2.2. 性质2

若 a\mid b,a\mid c ，则有 \forall\ x,y\in\mathbb{Z} ，满足 a\mid(bx+cy)

证明：

1.2.3. 性质3

若 a\mid b ，则 am\mid bm(m\ne0)

证明：

1.2.4. 性质4

若 \forall\ x,y\in\mathbb{Z} 满足 ax+by=1 ，且 a\mid n,b\mid n ，则 ab\mid n

证明：

1.2.5. 性质5

若 b=dq+c,q\in\mathbb{Z} ，那么 d\mid b 的充要条件为 d\mid c

证明1（若 d\mid b ，则 d\mid c）：

证明2（若 d\mid c ，则 d\mid b）：

2. 模运算

2.1. 定义

定义：有 \forall\ a,b\in\mathbb{Z},b\ne0 ，求 a\div b 的余数，称 a 模 b ，记作 a\bmod b

2.2. 性质

2.2.1. 性质1

2.2.2. 性质2

2.2.3. 性质3

证明：

2.2.4. 性质4

属于性质三的一种扩展

2.2.5. 性质5

如果 a\bmod b=c,d\ne0,d\in\mathbb{Z} ，则 (ad)\bmod(bd)=cd

证明：

2.2.6. 性质6

如果 a\bmod b=c,d\mid a,d\mid b ，则 (\dfrac{a}{d})\bmod(\dfrac{b}{d})=\dfrac{c}{d}

证明：

3. 同余

3.1. 定义

设 m 是给定的 \mathbb{Z}^+ ，若满足 m\mid(a-b) ，则称 a 与 b 对模 m 同余，记作 a\equiv b\pmod{m} ；若满足 m\nmid(a-b) ，则称 a 与 b 对模 m 不同余

如果将定义反过来，如果 a\equiv b\pmod{m} ，则 m\mid(a-b)（即 a\equiv b\pmod{m}\iff m\mid(a-b)）

证明1（已知 m\mid(a-b)）：

证明2（已知 a\equiv b\pmod{m}）：

3.2. 性质

3.2.1. 性质1

3.2.2. 性质2

如果 a\equiv b\pmod{m} ，那么 b\equiv a\pmod{m}

3.2.3. 性质3

如果 a\equiv b\pmod{m} ， b\equiv c\pmod{m} ，那么 a\equiv c\pmod{m}

3.2.4. 性质4

如果 a\equiv b\pmod{m} ，那么 (a+c)\equiv(b+c)\pmod{m}

证明：

3.2.5. 性质5

如果 a\equiv b\pmod{m} ，那么 (a-c)\equiv(b-c)\pmod{m}

证明方法类似于性质3

3.2.6. 性质6

如果 a\equiv b\pmod{m} ，那么 (ac)\equiv(bc)\pmod{m}

证明：

3.2.7. 性质7

如果 a\equiv b\pmod{m},c\mid a,c\mid b,(c,m)=1 ，那么 (\dfrac{a}{c})\equiv(\dfrac{b}{c})\pmod{m}

多说一句： (a,b)=\gcd(a,b)

证明：

3.2.8. 性质8

如果 a\equiv b\pmod{m} ，那么 (a^c)\equiv(b^c)\pmod{m}

证明：

另注： a^n-b^n=(a-b)\times\sum\limits_{i=0}^{n-1}a^ib^{n-i-1}

3.2.9. 性质9

如果 a\equiv b\pmod{m},c\equiv d\pmod{m} ，那么 (a+c)\equiv (b+d)\pmod{m}

证明：

3.2.10. 性质10

如果 a\equiv b\pmod{m},c\equiv d\pmod{m} ，那么 (ac)\equiv (bd)\pmod{m}

证明：

3.2.11. 性质11

如果 a\bmod p=x,a\bmod q=x,(p,q)=1 ，那么 a\bmod (pq)=x

证明：

4. 排列组合

咕咕咕

5. 筛法

5.1. 暴力筛

暴力筛，顾名思义，非常暴力的筛法（？

暴力筛是所有筛法的祖先，需要好好掌握

我们知道，一个数的倍数是一个合数，那么，我们可以进行一个遍历，将每一个数的倍数全部标记一遍，剩下的未被标记的就是质数了

#include<cmath>
#include<cstdio>
bool flag[200000005];
int n,ans,maxn;         //ans 用于统计质数数量, maxn 用于记录最大质数
int main(){
    scanf("%d",&n);
    for(int i=2;i<=sqrt(n);i++){            //只需枚举到 sqrt(n) 即可
                                            //原理很简单，假设 n=pq(p<q) ，那么，我们一定会在 p 之前的 q 枚举，而 p 的最大值又是 sqrt(n) ，所以枚举到 sqrt(n) 即可
        if(!flag[i]){           //未被标记，说明是质数
            ans++,maxn=i;           //更新数量和最大值
        }
        for(int j=i+i;j<=n;j+=i){           //将其倍数设为合数
            flag[j]=1;
        }
    }
    for(int i=sqrt(n)+1;i<=n;i++){          //因为遍历到 sqrt(n) 就结束了，后面的素数还要再来一个循环统计一次
        if(!flag[i]){
            ans++;
            maxn=i;
        }
    }
    printf("%d %d",ans,maxn);
    return 0;
}

然而，这显然不是最优筛法

5.2. 埃式筛

我们发现，假设一个合数 n 的其中一个质因子为 k ，那么 n=kx ， n 与其倍数必然已经在遍历到 k 的时候标记了，就不用再筛一遍了

所以，我们可以只用筛素数的倍数即可

#include<cmath>
#include<cstdio>
bool flag[200000005];
int n,ans,maxn;
int main(){
    scanf("%d",&n);
    for(int i=2;i<=sqrt(n);i++){
        if(!flag[i]){
            ans++;
            maxn=i;
        }
        if(flag[i]){            //当遍历到素数时，直接跳过，不进行遍历，剩下的和暴力筛一模一样
            continue;
        }
        for(int j=i+i;j<=n;j+=i){
            flag[j]=1;
        }
    }
    for(int i=sqrt(n)+1;i<=n;i++){
        if(!flag[i]){
            ans++;
            maxn=i;
        }
    }
    printf("%d %d",ans,maxn);
    return 0;
}

埃式筛已经够快了，但是，我们还有一个更快的解决方法

5.3. 欧拉筛

在埃式筛中，某些数依旧会被重复标记两次，比如 12 ，既会被 3 标记，也会被 2 标记

这时，我们尽量让每个数只被标记一次

而欧拉筛的原理是让每一个数被它的最小质因数标记

这里先上代码

#include<cstdio>
bool flag[200000005];
int n,ans,maxn;
int num[1500005],len;           //num 数组用于统计素数数组
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        if(!flag[i]){           //遍历到素数
            num[++len]=i,ans++,maxn=i;
        }
        for(int j=1;j<=len&&num[j]*i<=n;j++){           //枚举可能的最小质因数
            flag[num[j]*i]=1;           //标记
            if(i%num[j]==0){            //后文会有详细解释
                break;
            }
        }
    }
    printf("%d %d",ans,maxn);
    return 0;
}

这里解释一下这一段代码：

if(i%num[j]==0){
    break;
}

显然，这样已经违背了欧拉筛的原理，所以退出

6. gcd/lcm

6.1. 定义

公约数定义：一般设有 k 个数 a_1,a_2,a_3,\cdots,a_k\in\mathbb{Z}^+ ，如果 \exists d\in\mathbb{Z}^+ ，使 d\mid a_1,d\mid a_2,d\mid a_3,\cdots,d\mid a_k ，那么 d 为 a_1,a_2,a_3,\cdots,a_k 的公约数， d 是不唯一的

最大公约数：在 a_1,a_2,a_3,\cdots,a_k 的公约数集合中，最大的那个公约数称为最大公约数，如果是 a,b 两个元素的最大公约数，记为 \gcd(a,b) ，简写为 (a,b)

公因数与最小公因数的定义与公约数与最大公约数的定义类似，注意一下符号即可：

6.2. 一个定理

证明：

6.3. 欧几里得算法

一种非常常见的求最大公约数的算法：

代码形式：

#include<cstdio>
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d",gcd(n,m));
    return 0;
}
//非常简单，应该不用注释了吧

证明一下：

7. 裴蜀定理

这是一个非常常见的定理，相当重要

7.1. 基本定理

对于不定方程 ax+by=m(a,b,x,y,m\in\mathbb{Z}) ，其有解的充分必要条件为 \gcd(a,b)\mid m

证明1（已知 ax+by=m 有解）：

证明2（已知 \gcd(a,b)\mid m）：

咕咕咕

OI 中常见的有关裴蜀定理的出题形式（？

对于 \forall x,y\in\mathbb{Z} ，函数 \operatorname{f}(a,b)=ax+by 的最小 \mathbb{Z}^+ 的取值为 \gcd(a,b)

证明：

7.2. 引理及推论

7.2.1. 引理1

上台社死后我发现，我换一个表述方式似乎就没什么大问题了QAQ

如果 a,b\in\mathbb{Z}^+,(a,b)=1 ，则 \nexists 小于 b 的 k\in\mathbb{Z}^+ ，满足 b\mid ak

证明：

7.2.2. 推论

如果 a,b\in\mathbb{Z}^+,(a,b)=1 ，则 0,a,2a,\cdots,(b-1)a 这些数模 b 的余数互不相同

证明：

7.2.3. 引理2

如果 (a,b)=1 ，则 \exists\ k\in\mathbb{Z} ，满足 ak\bmod b=1

由推论可以很容易的得到该结论

8. 扩展欧几里得

扩展欧几里得（简称扩欧），是一种算法，一般封装为函数，其函数名为 exgcd

可以在已知 a,b\in\mathbb{Z} 的情况下，求不定方程 ax+by=\gcd(a,b) 的一组整数解，通常情况下用扩欧求得的解满足 xy<0

证明：

我们拿这道题来举个例子

8.1. 小练习

我们来处理一下原方程：

这样一来，直接套扩欧，再处理一下取值，基本上就没问题了

不 开 long long 见 祖 宗

#include<cstdio>
long long int a,b,c,x,y;
void exgcd(long long int a,long long int b){            //扩欧模板
    if(!b){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    long long int t=x;
    x=y;
    y=t-a/b*y;
}
int main(){
    scanf("%lld%lld",&a,&b);
    exgcd(a,b);
    if(x<0){            //处理结果，保证是最小的正整数
        x=x+(-x/b+1)*b;
    }else{
        x=x-x/b*b;
    }
    printf("%lld",x);           //输出
    return 0;
}
//水

9. 费马小定理

如果 p 为质数，且 a\bmod p\ne0 ，则 a^{p-1}\bmod p=1

证明：