2024.7.18 HASC2024 数论笔记

Air2011 · 2024-07-18 08:52:36 · 个人记录

本文章为本人所记录的笔记，供回忆用 。

---------- 前言

筛法

埃氏筛

基本思想

对于每一个合数而言，它肯定是其中若干个比它小的质数的倍数。于是我们对于每一个质数p，枚举它的倍数，把它的倍数打上标记，代表这个数为合数。

我们遍历所有的数，如果遇到一个没有打上标记的数，则此数为质数（前面没有任何一个质数是它的倍数），并用这个新质数来拓展标记。

优化

我们观察到，对于6而言，它会被2标记一次，又会被3标记一次，重复了，于是我们可以从质数p的p倍开始标记，复杂度O(n \ \log\log{n})。

code

bool isprime[N];
vector<int> p;
void ishi(){
    for(int i=2;i<=N;i++){
        if(!isprime[i]){
            p.push_back(i);     
            for(int j=i;j*i<=N;j++){
                isprime[i*j]=1;
            }
        }

    }
}

线性筛

基本思路

埃氏筛可能还是会给一个数重复打标签，如12会被2打一次，3打一次，于是就重复了。

显然，我们只需要让每个数的最小质因子给这个数打上标签即可实现O(n)复杂度。对于任意一个数而言，我们使用当前的质数去拓展肯定要比用合数去拓展的重复率低，但还不够。对于任意一个数，如果当前我们枚举的质数为此数的某个因数，那么接下来的倍数一定会被我们枚举到的质数所打上标签，于是便可退出循环，实现O(n)复杂度。

code

bool isprime[N];
vector<int> p;
void get(){
    for(int i=2;i<=n;i++){
        if(!isprime[i]){
            p.push_back(i);
        }
        for(int j=0;j<p.size()&&i*p[j]<=n;j++){
            isprime[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}

gcd & lcm

概念

证明

设x=P_1^{C_{1^1}}P_2^{C_{2^1}}P_3^{C_{3^1}} ... P_k^{C_{k^1}},y=P_1^{C_{1^2}}P_2^{C_{2^2}}P_3^{C_{3^2}} ... P_k^{C_{k^2}}，则