数论基础知识

标签（空格分隔）： 数论 笔记

---

质数

素数判定

试除法

因为合数\(n\)必定存在一个因数\({a\in(1,\lfloor\sqrt n\rfloor]}\)

所以直接试除所有可能的\(a\)即可

Miller-Rabin算法

讲解见\(\mathtt{blog}\)

inline char Check(re int x,re int p){
    if(qpow(p%x,x-1,x)^1)return 0;
    re int k=x-1,t;
    while(!(k&1)){
        if((t=qpow(p%x,k>>=1,x))^1&&t^(x-1))return 0;
        if(!(t^(x-1)))return 1;
    }
    return 1;
}

素数筛法

埃氏筛法

未优化版

考虑对于每个数\(i\),若未被标记则为质数

然后标记他的每一个倍数\(i\cdot k(k\in[1,\lfloor \frac{n}{i}\rfloor])\)

有一个小小的优化若\(k<n\)则\(i\cdot k\)一定在\(i=k\)时被筛

因此\(k\in[i,\lfloor \frac{n}{i}\rfloor]\)

inline void Sieve(re int n){
    re int i,j;
    for(i=2;i<=n;++i){
        if(!vis[i])pri[++*pri]=i;
        for(j=i*i;j<=n;j+=i)vis[j]=1;
    }
}

复杂度为\(~O(\frac{n}{1}+\frac{n}{2}+\cdots+\frac{n}{n})=O(n\log n)\)

优化版

考虑只用质数去更新倍数

inline void Sieve(re int n){
    re int i,j;
    for(i=2;i<=n;++i){
        if(!vis[i])pri[++*pri]=i;else continue;
        for(j=i*i;j<=n;j+=i)vis[j]=1;
    }
}

这个优化实质上优化了复杂度\(~O(n\log\log n)\)

线性筛

首先我们对于每个数\(i\)用筛出的质数相乘来筛

考虑记录每一个合数的最小合数\(v_i\)

那么当我们筛\(i\)的素数倍时若素数\(p>v_i\)那么\(i\cdot p=v_i\cdot k\cdot p\)其实已经被\(v_i\)筛过了

inline void Sieve(re int n){
    re int i,j;
    for(i=2;i<=n;++i){
        if(!vis[i])pri[++*pri]=i;
        for(j=1;j<=*pri;++j){
            if(i*pri[j]>n||pri[j]>vis[i])break;
            vis[i*pri[j]]=pri[j];
        } 
    }
}

其实不用记录\(v_i\)考虑\(v_i\)一定是整除\(i\)的第一个质数表中质数

inline void Sieve(re int n){
    re int i,j;
    for(i=2;i<=n;++i){
        if(!vis[i])pri[++*pri]=i;
        for(j=1;j<=*pri;++j){
            if(i*pri[j]>n||!(i%pri[j]))break;
            vis[i*pri[j]]=1;
        } 
    }
}

非常优秀但很慢的\(~O(n)\)

例题

\(\mathtt{pub1632}\):裸的
\(\mathtt{pub1633}\):筛\(\sqrt n\)的素数,然后再用这些素数来筛值大间距小区间

质因数分解

【法一】试除

直接\(n\sqrt n\)试除

【法二】离线筛素数

首先筛出\((1,\sqrt n]\)的质数
然后\(~O(n \frac{\sqrt n}{\log n})(\)假设素数个数均摊\(\frac{\sqrt n}{\log n}\)个\()\)回答询问

【法三】筛法中处理

在埃氏筛的过程中用\(i,pri_j\)筛到\(i\cdot pri_j\)为其累加质因子个数

具体来说\(count_{i\cdot pri_j,pri_j}+=count_{i,pri_j}+1\)

【补充】分解阶乘

考虑\((1,n]\)内每一个质数\(p\)

\(p\)的个数为\(\displaystyle{\sum_{i=1}^{\infty}\lfloor\frac{n}{p^i}\rfloor}\)

例题

\(\mathtt{pub1636}\):唯一分解定理运用+搜索
\(\mathtt{pub1637}\):阶乘分解
\(\mathtt{pub1180}\):简单质因数分解运用

约数

gcd and lcm

定义

若\(\displaystyle{a=\prod_{i=1}^k p_i^{ca_i}\\b=\prod_{i=1}^k p_i^{cb_i}}\)

则\(\displaystyle{(a,b)=\prod_{i=1}^k p_i^{\min\{ca_i,cb_i\}}}\\\)
\(\displaystyle{~[a,b]=\prod_{i=1}^k p_i^{\max\{ca_i,cb_i\}}}\)

性质

• \(1.(a,b)\cdot [a,b]=a\cdot b\)
  【证明】\(\displaystyle{\prod_{i=1}^k p_i^{\min\{ca_i,cb_i\}}\cdot\prod_{i=1}^k p_i^{\max\{ca_i,cb_i\}}\\=\prod_{i=1}^k p_i^{\min\{ca_i,cb_i\}+\max\{ca_i,cb_i\}}\\=\prod_{i=1}^k p_i^{ca_i+cb_i}}\)
• \(2.(a,b)=(b,a\mod b)\)

例题

\(\mathtt{pub1640}\):高精度更相减损术
\(\mathtt{pub1645}\):质因数分解后利用\(gcd/lcm\)性质分类讨论一下即可