数论基础

· · 个人记录

欧拉筛

时间复杂度：O(n) (4e7 ~ 5e7都可过)

难度：⭐

核心思想：对埃筛优化，对于一个合数我们强制它只能被较小的 质数因子筛掉

{\color{Blue}{eg. 6=2×3，强制6只能被2筛除}}

代码实现

for(int i = 2;i <= n;i ++){
    if(!vis[i])pri[++cnt] = i;
    for(int j = 1;j <= cnt;j++){
        vis[i * pri[j]] = 1;
        if(i % pri[j] == 0)break;
    }
}

扩展欧几里德

时间复杂度：O(\log n)

难度：⭐⭐

核心思想：

对于方程:{\huge{ax + by = c}}求某个特定解

此时对于方程有解有一个特定条件：{gcd(a,b)|c}

{\color{Blue}{\footnotesize{简单证明}: 等式两边同÷gcd(a,b)可以得到（确保c ÷ gcd(a,b)为整数）}}

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
void exgcd(int &x,int &y){
    if(y == 0){
        x = 1;y = 0;
        return ;
    }
    int _x = y,_y = x % y;
    exgcd(_x,_y);
    y = _x - (x / y) * _y;
    x = _y;
    return ;
}
signed main(){
    cin >> n >> m;
    exgcd(n,m);
    cout<<n<<' '<<m<<endl;
    return 0;
}

中国剩余定理

时间复杂度：O(n\log n)

题目传送门