问题标题: 酷町堂：算法讲解7：数论综合

数论综合

数论目录(可能有些不是数论):

1.基**概念

2.快速幂

3.质数筛

4.唯一分解定理

5.欧几里得定理&扩展欧欧几里得

[1]基**概念

1.整除：a,b∈Z，b/a∈Z，可得:a|b（后面有用）

2.因倍数：当a|b时，b是a的倍数，a是b的因数

3.任意一个整数m可以记作m=kn+r，m,k,n,r∈Z，r是m/k得到的余数

4.当a%k=b%r时，a≡b（≡同余符号）a,b,k,r∈Z

5.余数的**质:

1.(a mod p±b mod p) mod p=(a±b) mod p

2.(a mod p)(b mod p) mod p=ab mod p

3.C++中mod保留符号

[2]快速幂

#include<iostream>
using namespace std;
int main(){
    int n,m,t=1;//求n的m次方
    cin>>n>>m;
    int x=n;
    if(m==0)cout<<1;
    while(m!=0){
        bool cmp=(bool)(m%2);//转二进制,判断最后一位是1还是0 
        m=m>>1;//二进制删去最后一位 
        cout<<x<<"  ";//输出检测每一位的x 
        if(cmp==1)t*=x;//如果最后一位是1就乘 
        x*=x;//x转化为下一位 
    } 
    cout<<endl<<t;
    return 0;
}

[3]质数筛(2-n)

初阶质数筛:遍历2-n,一个一个判断

进阶质数筛:埃氏筛:从2开始，将所有数的倍数标记，没标记的就是质数

··················································

终极质数筛:线**筛：

基本思想：i从2遍历到n，将所有比i小的质数的i倍数标记上，一直标记到这个比i小的质数是i的因数为止（防止重复标记导致超时）

具体代码

#include<iostream>
using namespace std;
bool m[100000001];//标记 
int s[100000001];//记录素数 
int main(){
    //O(n)做法: 
    int n,t,cnt=0;//cnt:有多少个素数 
    cin>>n>>t;
    for(int i=2;i<=n;i++){
        if(m[i]==0)s[cnt++]=i;//记录素数 
        for(int j=0;j<cnt&&i*s[j]<=n;j++){//遍历素数,标记 
            m[i*s[j]]=1;//标记 
            if(i%s[j]==0)break;//防止重复标记 
        }
    }
    for(int i=1;i<=t;i++){
        int k;
        cin>>k;
        cout<<s[k-1]<<endl;
    }
    return 0;
} 

[4]唯一分解定理（复赛用有奇效）

定理1:任何一个整数可以分解为一些素数的乘积，并且分解方式一定

定理2:a×b=a和b的最大公约数×a和b的最小公倍数

定理3:裴蜀定理:ax+by=n有整数解等价于：a,b的最大公约数整除于n

定理4:当a,b∈Z且a,b互质时，任何大于a×b-a-b的数都可以记作ax+by(x,y≥0)，同时a×b-a-b是最大的不能表示成为ax+by的数（P3915[NOIP2017]小凯的疑惑）

[5]欧几里得定理&扩展欧

欧几里得定理：辗转相除法求a,b的最大公约数：gcd(a,b)=gcd(b,a mod b)，当a=0时，b就是最大公约数(递归)

扩展欧几里得算法：求二元一次不定方程的整数解（前方有高中题目，谨慎观看~）

求：ax+by=c（a,b,c,d,e∈Z）

常规解法：找特解，带回求解

扩欧定理：如果ax+by=c有解则gcd(a,b)是c的倍数

扩欧解法：递归寻找gcd(a,b)知道x=0，则y=1，然后回溯找其他的整数解

日常打广告：

在博客内观看更优：https://www.luogu.com.cn/blog/Luogu-Blog-Org/

在博客内观看更优：https://www.luogu.com.cn/blog/Luogu-Blog-Org/

在博客内观看更优：https://www.luogu.com.cn/blog/Luogu-Blog-Org/