数论学习笔记

wangyichen_0711 · 2026-08-15 17:29:05 · 算法·理论

updata on 2026/8/26 : 修改格式问题

下文内容是在大纲中 NOI 难度（可能包含）以下的数论算法的内容、证明、应用及例题。

这是我第四遍听数论了，再不会本人真该退役了同志们。

感谢 @Mingoal 老师的讲解，文中的大部分内容来自老师的课件，还有机房大佬 @Natural_Selection 对我没听懂的裴蜀定理的讲解证明，文章在这，我的文章也有引用这里的部分内容，一定要先把它看完。

扩展欧几里得 (exgcd)

内容

通过上面的文章，我们了解到了只要满足裴蜀定理的方程，就必定有解，但我们更希望能求出这样的一组特解到底是什么，于是人们在欧几里得算法的基础上推导出了扩展欧几里得（exgcd）。

:::warning[什么是欧几里得算法？] 欧几里得算法，又称辗转相除法，通过递归的方式求解两个数的最大公约数，即：

当 x=0 时不难发现答案为 y，之后顺次返回即可。

代码如下实现：

int gcd(int a,int b){b==0?a:return gcd(b,a%b);}

:::

1. 边界：b=0 时 \gcd(a,0)=a，取 (x=1,y=0)，即 a\times 1+0\times 0=a 成立。
2. 递归假设：已求出 bx'+(a \bmod b)y'=\gcd(b,a\bmod b) 的解为：

4. 带入 a \bmod b =a-\lfloor \frac{a}{b}\rfloor b，展开并进行整理：

原方程 ax+by=\gcd(a,b) 转化成 bx'+(a\bmod b)y'=ay'+b(x'-\lfloor \frac{a}{b}\rfloor y')=\gcd(a,b)。

4. 对照原方程，此时方程的解又一次转化为了：

递归层数为 O(\log \min(a,b))。

这里非常抽象难懂，可以结合后文的例题代码理解。

应用

• 应用 1：解线性不定方程

无整数解 等价于 d 不整除 c（裴蜀定理推论 1）。

• 应用 2：解同余方程

exgcd 求出特解 x_0 后，通解 x=x_0+bt，

最小正整数解为 (x_0 \bmod b+b)\bmod b (若结果为 0 则取 b)。

这就是后文 逆元 求解的同余方程形式。

可能你会怀疑如果 a,b 为负怎么办，可以把 a,b 上的负号加到通解上，最后转化一下即可。

• 应用 3：求乘法逆元

• 与加减乘相容：例如 8\bmod 7 *3 =1*3=3 且 8*3\bmod7=24\bmod 7=3。

最好应养成如下三个习惯（用代码表示）：

1. 加减乘三种运算时取模应为：

• 加法：(a+b)%m=(a%m+b%m)%m
• 减法：(a-b)%m=(a%m-b%m)%m
• 乘法：(a*b)%m=((a%m)*(b%m))%m

2. 将结果归一到 [0,m-1]

• C++ 对 % 对负数返回负余数，需调整 return (x%m+m)%m;

3. 乘法先取模防溢出

• 连乘前先对每个因子取模，中间结果也每步取模：res=res*a%m;
• 当 m 很大时，可以使用类似高精度乘法的龟速乘或者 _int128（后文讲解 P3868 需要使用，但貌似同学说 __int128 是有误的？）

内容 of 逆元

像上文所说，除法并不适配取模运算，但我们有时也需要使用它，于是我们会寻找一个在取模运算下仍能正常使用的乘法。

于是我们有了一下定义：

若整数 x 满足 ax \equiv 1 \bmod m，则称 x 为 a 在模 m 意义下的乘法逆元，记作 a^{-1}。

其作用即为在模意义下进行除法，把除法变为乘法：a \div b \equiv ab^{-1} \bmod m。

性质 of 逆元

1. 存在条件：\gcd(a,m)=1。因为 ax \equiv 1 \bmod m 等价于 ax+my=1，这是裴蜀定理推论 3，(原性质 互质 等价于 可组合出 1)———— 所以逆元就是裴蜀定理的延续。 2. 唯一性：若 x_1,x_2 都是你愿，则 a(x_1x_2) \equiv 0 \bmod m，由 \gcd(a,m)=1 得 m \mid (x_1-x_2)，即逆元在模 m 意义下唯一。

代码实现 of 逆元

• 线性递推（批量）

推导：令 p=ki+r，ki+r=0，两边乘逆元，得到 i^{-1}=-kr^{-1}，即 inv[i]=(p-p/i)*inv[p%i];，由规定不难发现 p \bmod i < i，总用已经求得的值，时间复杂度 O(n)。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL  long long //[(p-p/i)可能炸int]
using namespace std;
LL inv[3001000];
signed main(){
  //[p必须为质数且n<p，否则p%i>=i导致失败!!]
    int n;LL p; cin>>n>>p; 
    inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;i++)cout<<inv[i]<<" ";
    return 0-0;
}

• 扩展欧几里得（单点）

要点：不难发现求逆元等价于 ax+by=1。任意（互质）模数，时间复杂度 O(\log m)，适合单点。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
using namespace std;
LL exgcd(LL a,LL b,LL &x,LL &y){
  if(b==0){x=1,y=0;return a;}
  LL g=exgcd(b,a%b,y,x);
  y-=a/b*x;
  return g;
}
LL inv(LL a,LL m){
  LL x,y;
  exgcd(a,m,x,y);
  return (x%m+m)%m;
}

• 费马小定理（m 为质数）

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL  long long
using namespace std;
LL ksm(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }
    return ans;
}
LL inv(LL a,LL p){
    return ksm(a,p-2,p);//不明白这里的后文会讲解
}

费马小定理

内容

或者是一般形式

对任意整数 a 恒成立。

这个定理被称为费马小定理。

:::info[证明（选读）]

1. 考虑集合 S=\set{a,2a,3a,...,(p-1)a}：若 ia \equiv ja (\bmod p) \set{0<i<j<p-1}，则 p \mid (j-i)a，再由 p 不整除 a 且 p 为质数，发现与 0<j-i<p 矛盾。
2. 故 S 中元素模 p 两两不同余且均不为 0，即恰好是 \set{1,2,3,...,p-1} 的一个序列。

3. 两边取乘积：a^{p-1}(p-1)!\equiv (p-1)! (\bmod p)。因为 \gcd((p-1)!,p)=1，两边约去 (p-1)!，即得 a^{p-1}\equiv 1 (\bmod p)。

推论及应用

• 推论 1：模质数求逆元

由 1\equiv a^{p-1} \bmod p 左右两边同时除以 p 得到。

• 推论 2：指数降幂

1. 令 res 初始为 n, 从 2 试除到 \sqrt{n}；找到每一个质因子 p：res=res/p*(p-1)，并除尽 p。
2. 试除结束后若剩余 x>1 则说明剩下的这个 x 是大于 \sqrt n 的质因子，res=res/x*(x-1)。

时间复杂度 O(\sqrt{n})。

• 批量求欧拉函数

应用线性筛的思想，不难发现，对于某个数 n，它的欧拉函数一定与自己的因数相关。我们只考虑最小的质因数，令这个数为 p，则每 p 个数就会出现 \varphi(p) 个与它互质的数，所以 \varphi(n)=\varphi(n/p)*(p-1)。

我们从小到大枚举数字并分类讨论，如果是质数由性质可知答案，否则暴力向上翻倍枚举，直到找到翻倍的数 n 是某一个已发现的质因数 p 的倍数，就令它的答案为 \varphi(n/p)*p，因为它比原数更多了一倍。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
using namespace std;
int pri[1001000],cnt,phi[1001000];
bool notpri[1001000];
int eulerSieve(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!notpri[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
            int p=pri[j],ip=i*p;
            notpri[ip]=1;
            if(i%p==0){phi[ip]=phi[i]*p;break;}
            phi[ip]=phi[i]*(p-1);
        }
    }
}

内容 of 欧拉定理

这个公式名为欧拉定理。

可以理解成素数个数在一定数字内不断循环。

当 m 为质数时，\varphi(m)=m-1，退化为费马小定理。

:::info[证明（选读）] 使用了与费马小定理相似的证明套路。

1. 设 1\leq b_1<b_2<...<b_{\varphi(m)}\leq m 是 1...m 中所有与 m 互质的数（共有 \varphi(m) 个）
2. 对每个 i 考察 ab_i：由 \gcd(a,m)=1 且 \gcd(b_i,m)=1 可知 \gcd (ab_i,m)=1；且 ab_i 模 m 两两不同 [若 ab_i=ab_j \equiv s (\bmod m)] ，则 m \mid a(b_i-b_j)，由 \gcd(a,m)=1 得 m \mid (b_i-b_j)，矛盾。

3. 故 \set{ab_1,ab_2,...,ab_{\varphi(m)}} 模 m 后认为 \set{b_1,b_2,...,b_{\varphi(m)}} 的序列。取乘积 a^{\varphi(m)}\set{b_1,b_2,...,b_{\varphi(m)}}\equiv \set{b_1,b_2,...,b_{\varphi(m)}} (\bmod m)；因为 \Pi b_i 与 m 互质可约去，得 a^{\varphi(m)}\equiv 1 (\bmod m)

内容 of 扩展欧拉定理

这个在欧拉定理公式基础上变形得来的公式名为扩展欧拉定理。

其用途在读不完的超大整数上。

2. 边读边做两件事：与 \varphi(m) 比较大小，判断是否 b\geq \varphi(m)；对 \varphi(m) 取摸得到 b'。
3. 若 b\geq \varphi(m)：ans=a^{b'+\varphi(m)}，否则 ans = a^b，用快速幂实现。

例题 of 扩展欧拉定理

• P5091 【模板】扩展欧拉定理模版题，代入定理即可。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL  long long
using namespace std;
LL a,m,phi=1,now;
bool flag=0;
LL ksm(LL x,LL y){
    LL ans=1;
    for(;y;y>>=1,x=x*x%m){if(y&1)ans=ans*x%m;}
    return ans;
}
signed main(){
    cin>>a>>m;
    a%=m;LL n=m;
    for(LL i=2;i*i<=n;i++){
        if(n%i)continue;
        phi*=i-1;n/=i;
        while(n%i==0)phi*=i,n/=i;
    }
    if(n>1)phi*=n-1;
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    while(now=now*10ll+(ch-'0'),(ch=getchar())>='0'&&ch<='9')if(now>=phi)flag=1,now%=phi;
    if(now>=phi)flag=1,now%=phi;
    if(flag)now+=phi;
    cout<<ksm(a,now);
    return 0-0;
}

• P3934 [Ynoi Easy Round 2016] 炸脖龙 I

不难发现，如果一个个去乘一定会炸时间，考虑使用扩展欧拉定理进行降幂。

每次递归的处理靠左一点的幂次，直到相同。

对于求和，我们可以考虑使用树状数组维护。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL phi[20000005],prime[20000005],cnt,f[500005],a[500005],n,m;
bool isnotpri[20000005];
LL lowbit(LL x){return x&-x;}
void upd(LL x,LL k){while(x<=n){f[x]+=k;x+=lowbit(x);}}
LL query(LL x){LL sum=0;while(x>=1){sum+=f[x];x-=lowbit(x);}return sum;}
LL ksm(LL a,LL b,LL p){
    if (p==1)return 0;
    if (a==0||a==1)return a;
    LL ans=1;bool flag=0; 
    if(a>=p){flag=1;a%=p;}
    if(b>=32)flag=1;
    else{LL tmp=1;for(int i=0;i<b;i++){tmp*=a;if(tmp>=p){flag=1;break;}}}
    if(b>=phi[p])flag=1,b=b%phi[p]+phi[p];
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }
    if(flag)ans+=p;
    return ans;
}
LL solve(LL l,LL r,LL p){
    LL tmp=query(l);
    if(p==1) return 1;//重要特判！！
    if(l==r) return tmp>=p?tmp%p+p:tmp;
    return ksm(tmp,solve(l+1,r,phi[p]),p);
}
signed main(){
    cin>>n>>m;
    for(LL i=1;i<=n;i++){cin>>a[i];upd(i,a[i]);upd(i+1,-a[i]);} 
    isnotpri[1]=1;phi[1]=1;
    for(LL i=2;i<=20000000;i++){
        if(!isnotpri[i]){prime[++cnt]=i;phi[i]=i-1;}
        for(LL j=1;j<=cnt;j++){
            if(i*prime[j]>2e7)break;
            isnotpri[i*prime[j]]=1;
            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(LL i=1;i<=m;i++){
        LL opt;cin>>opt;    
        LL l,r,x;cin>>l>>r>>x; 
        if(opt==1)upd(l,x),upd(r+1,-x);
        else cout<<solve(l,r,x)%x<<endl;
    }
    return 0;
}

• P2158 [SDOI2008] 仪仗队

不难发现，只要任意一个点 (x,y) 与另一点 (x',y')，其 \gcd(\lvert x-x'\rvert,\lvert y-y'\rvert) 必须为 1。否则不会被对方看见。

对于每个非终点的横坐标 i，它都会对答案作出 \varphi(i) 的贡献，又因为方格左右对称，求和后再乘以 2，后加上一个起点就是最终答案。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL  long long
using namespace std;
const int N=40010;
bool isnpri[N];
int cnt,pri[N],phi[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)phi[i]=i;
    for(int i=2;i<=n;i++)
        if(phi[i]==i)
            for(int j=1;j*i<=n;j++)
                phi[i*j]=phi[i*j]/i*(i-1);
    LL ans=0;
    for(int i=1;i<n;i++)ans+=phi[i];
    cout<<(n==1?0:ans*2+1);
}

数论分块

内容

对于固定的 n，我们不难注意到 \lfloor\frac{n}{i}\rfloor 在 i=1,2,...,n 上只有 2\sqrt{n} 个不同取值。

因此当我们求 \sum g(\lfloor\frac{n}{i}\rfloor) 时，取值相同的 i 可以合并成一个块计算，最后只会留下 \sqrt{n} 个块，这样的思想我们称其为分块。

:::info[为什么只有 \sqrt{n} 钟取值]

1. 当 i \leq \sqrt{n} 时，i 本身有且仅有 \leq \sqrt{n} 个，因此 \lfloor\frac{n}{i}\rfloor 当然最多只有 \sqrt n 个不同取值。
2. 当 i > \sqrt{n} 时，\lfloor\frac{n}{i}\rfloor \leq \frac{n}{i}<\sqrt{n}，取值落在 [0,\sqrt{n}] 的范围内，也至多只有 \sqrt n 个不同取值。

3. 合起来，不同取值的个数一定 \leq 2\sqrt{n}。

我们还可以的得到用来计算右端点的公式（取值相同的一段区间）。

若左端点为 l，则右端点为 \lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor，其这段区间内的取值均为 \lfloor \frac{n}{i}\rfloor。

代码实现

LL block(LL n){
  LL ans=0;
  for(LL l=1,r;l<=n;l=r+1){
    LL t=n/l;
    r=n/t;//右端点
    ans+=(t-l+1)*t;//块内贡献
  }
}

当和式中同时出现 \lfloor \frac{n_1}{i}\rfloor 以及 \lfloor \frac{n_2}{i}\rfloor 时，取较小值（取较大值可能会漏掉贡献）。

取模拆除法：k\bmod i = k-i \lfloor \frac{k}{i}\rfloor。

例题

• P2261 [CQOI2007] 余数求和

注意到，原式进行如下变化：

由上文定义可知后面一项中 \lfloor\frac{k}{i}\rfloor 只有 \sqrt{k} 种取值，枚举快的左端点 l，t=\lfloor\frac{k}{l}\rfloor，若 t=0（即 l>k），则 r=n 直接结束；否则令 r=\min(\lfloor\frac{k}{t}\rfloor,n)。

对于每一个块 [l,r]，\lfloor\frac{k}{i}\rfloor = t 恒成立，因此贡献为 t[l+(l+1)+...+r]=\frac{t(l+r)(r-l+1)}{2}。

最终时间复杂度 O(\sqrt{k})。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n,k,ans;
signed main(){
   cin>>n>>k;
   for(LL l=1,r,t;l<=n;l=r+1){
    t=k/l;
    r=t?min(k/t,n):n;
    ans-=t*(r-l+1)*(l+r)/2;
   }
   cout<<ans+n*k;
   return 0;
}

离散对数 (BSGS 大步小步算法)

内容

为了求解形如 a^x \equiv b (\bmod p) 的不定方程，我们定义出如下算法：

令 m=\lceil\sqrt{p} \rceil，这样可以将 x 写为 x=im-j，代入原方程并乘以 a^j 得到 a^{im} \equiv ba^j (\bmod p)，接下来进行如下操作：

• 不断枚举 j=0,1,...,m-1，把 ba^j\bmod p 存入哈希表，值为 j（重复则保留 j 最大的）。 （Baby step）
• 枚举 i=1,2,...,m，查询 a^{im} 是否在哈希表中；命中 j 则解为 x=im-j, i 从小到大第一个即为最小解。 （Giant step）
• 空间时间复杂度 O(\sqrt p)，i 从 1 到 m 覆盖了 x 的整个取值范围 [0,p)。

于是，这种算法便被称为大步小步算法（BSGS）。

可以把第 1 步具象成从终点往中间连边，第 2 步具象成从起点往中间找边，一种非常经典的 折半搜索（Meet in Middle） 思想。

例题

• P3846 【模板】BSGS / [TJOI2007] 可爱的质数

纯板子，不作题目内容讲解。

//今夜は月が綺麗ですね
#include <bits/stdc++.h>
#define LL  long long
using namespace std;
LL BSGS(LL a,LL b,LL p){
    a%=p,b%=p;
    if(b==1)return 0;
    LL m=ceil(sqrt((double)p));
    map<LL,LL>mp;//[unordered_map会更快]
    LL cur=1,step=cur;//cur代表Baby Step,重复保留大j (步骤1)
                    //giant从i查a^(im)（步骤2）
    for(LL j=0;j<m;j++)mp[cur*b%p]=j,cur=cur*a%p;
    for(LL i=1;i<=m;i++,cur=cur*step%p)
      if(mp.count(cur))return i*m-mp[cur];
    return -1;
}
signed main(){
    LL a,b,p;
    cin>>p>>a>>b;
    LL ans=BSGS(a,b,p);
    if(ans==-1)cout<<"no solution";
    else cout<<ans;
    return 0-0;
}

(扩展) 中国剩余定理 (CRT / exCRT)

内容 of CRT

当我们遇到了同余方程组应如何求解呢？我们进行如下构造：

• 现在有同余方程组 x \equiv b_i (\bmod a_i),i=1...n，保证 a_i 两两互质。
• 令 M=a_1\times a_2 \times ...\times a_n，即所有模数之积。
• 对每个 M_i=\frac{M}{a_i}，表示去掉了第 i 个模数，求 M_i 模 a_i 的逆元 t_i (M_it_i\equiv 1\bmod a_i，exgcd)。
• 最后构造答案：

这样的构造方式被称为中国剩余定理（CRT）。

性质 of CRT

:::info[为什么 \sum b_iM_it_i 可以满足所有方程？]{open} 固定第 k 个方程，看 x 模 a_k：对 j 不等于 k，M_j=\frac{M}{a_j} 是 a_k 的倍数（因为 a_j 与 a_k 互质且 a_j 在乘积中），故第 j 项 b_jM_jt_j\equiv 0 \bmod a_k，全部消失；只剩下第 k 项的 b_kM_kt_k\equiv b_k\times 1 \equiv b_k\bmod a_k。

:::info[为什么解在模 M 意义下唯一？]{open} 若 x,y 都是解，则对每个 i:a_i\mid(x-y)。