浅谈数学（二）

Furina_Aurora · 2026-10-02 11:22:44 · 算法·理论

前言

往期回顾

《浅谈数学》 by Stellar_River。

~~不得不说，SR 大佬也是太能肝了，把部分的中等数论都给写了。~~

编写人员

主编：Furina_Aurora；
副主编：Stellar_River & _m2b _\。

扩展欧几里得

本章由 Furina_Aurora 编写。

【前置】裴蜀定理

对于任意的两个不全为 0 的整数 a,b，记 g=\gcd(a,b) ，则必然存在整数 x,y 使得 ax+by=g。

特别地，a 与 b 互素当且仅当存在整数 x,y 满足 ax+by=1。

这一定理在上一期中已经介绍过了。

【例题】

:::info[题目描述]{open} 输入两个不同时为 0 的整数 a,b，请求出满足下方这个式子的 g,x,y：

ax+by=g=\gcd(a,b)

::: :::success[解法]{open} 上一期提供的伪代码：

inline auto ExEuclid(auto a,auto b){
    if(b==0)return abs(a),sign(a),0;
    auto x1,y1;
    x1=y1=g=ExEuclid(b,a%b);
    x=y1;
    y=x1-(a div b)*y1;
    return g,x,y;
}

现在，我们给出了完整的代码：

inline int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=(a>0?1:-1),y=0;
        return abs(a);
    }
    int g=exgcd(b,a%b,x,y),tot=x;
    x=y,y=tot-(a/b)*y;
    return g;
}

::: :::success[证明]{open} 情况 1： a>0,b>0

上一期中已经给出证明，本期不再赘述。

情况 2： a,b 一正一负

我们不妨设 a>0,b<0，令 b_1=-b>0，此时 \gcd(a,b)=\gcd(a,b_1)，由情况 1 得，必然存在整数 x_1,y_1 满足：

ax_1+b_1y_1=\gcd(a,b_1)=\gcd(a,b)

将 b_1=-b 代入，整理可得：

ax_1+b\cdot (-y_1)=\gcd(a,b)

取 x=x_1,y=-y_1，显然，x,y 均为整数，满足裴蜀定理。

同理，若 a<0,b>0，令 a_1=-a>0，也可以构造出合法整数解。

情况 3： a<0,b<0

令 a_1=-a>0,b_1=-b>0，此时 \gcd(a,b)=\gcd(a_1,b_1)，由情况 1 得，必然存在整数 x_1,y_1 满足：

a_1x_1+b_1y_1=\gcd(a_1,b_1)=\gcd(a,b)

将 a_1=-a,b_1=-b 代入，整理可得：

a\cdot (-x_1)+b\cdot (-y_1)=\gcd(a,b)

取 x=-x_1,y=-y_1，显然 x,y 都是整数，满足裴蜀定理。

:::

欧拉函数

本章由 Stellar_River 编写。

【定义】

设 n\in \Z^+，函数 \varphi(n) 定义为不超过 n 且与 n 互素的正整数的个数，即

\varphi(n)=\#\{ 1\le k\le n\ |\ \gcd(k,n)=1 \}

特别地，我们规定 \varphi(1)=1

【性质】

不妨设 n,m,k\in \Z^+

积性函数：若 \gcd(m, n) = 1，则 \varphi(mn) = \varphi(m)\varphi(n)，可用中国剩余定理证明；
素数幂的情形： \varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)
一般公式：
若 n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}，则 \varphi(n) = \prod_{i=1}^k p_i^{\alpha_i} \left(1 - \frac{1}{p_i}\right) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)
高斯定理： \sum_{d|n} \varphi(d) = n
证明：枚举因子 d，恰好有 \varphi(d) 个不超过 n 的正整数 k 满足
\gcd(k, n) = \frac{n}{d}
【例题】GCD

:::info[题目描述]{open}
令 P 表示所有素数构成的集合；

给定正整数 n，求 1\le x,y\le n 且 \gcd(x,y) 为素数的数对 (x,y) 有多少对。
:::success[如何求解]{open}
设最终答案为 \text{ans}，则
$$
\begin{aligned}
\text{ans}
&= \sum{p \in P,p\leq n} \sum{i=1}^{n} \sum_{j=1}^{n} \llbracket \gcd(i, j) = p \rrbracket \
&= \sum{p \in P,p\leq n} \sum{i=1}^{\lfloor n/p \rfloor} \sum_{j=1}^{\lfloor n/p \rfloor} \llbracket \gcd(i, j) = 1 \rrbracket \
&= \sum{p \in P,p\leq n} \left( 2 \left( \sum{i=1}^{\lfloor n/p \rfloor} \sum_{j=1}^{i} \llbracket \gcd(i, j) = 1 \rrbracket \right) - 1 \right) \
&= \sum{p \in P,p\leq n} \left( 2 \left( \sum{i=1}^{\lfloor n/p \rfloor} \varphi(i) \right) - 1 \right)
\end{aligned}
$$
:::
## 欧拉定理
本章由 Stellar_River 编写。
### 【定义】欧拉定理
若 a, n \in \mathbb{Z}^+ 且 \gcd(a, n) = 1，则
$$
a^{\varphi(n)} \equiv 1 \pmod{n}
$$
### 【定义】费马小定理
若 a, p \in \mathbb{Z}^+ 且 p 是素数，且 p\nmid a，则
$$
a^{p-1} \equiv 1 \pmod{p}
$$
### 【推论】费马小定理
若 a, p \in \mathbb{Z}^+ 且 p 是素数，且 p\nmid a，则
$$
a^{-1} \equiv a^{p-2} \pmod{p}
$$

因此，可以使用快速幂求模素数下的逆元。

【证明】欧拉定理

设 1 到 n 中与 n 互素的正整数为 r_1, r_2, \dots, r_{\varphi(n)}，它们构成模 n 的一个简化剩余系
由于 \gcd(a, n) = 1，当这些数分别乘以 a 后，得到的数

ar_1, ar_2, \dots, ar_{\varphi(n)}

在模 n 意义下仍然构成一个简化剩余系（即它们模 n 两两不同余，且每个数仍与 n 互素）
因此，这两个集合在模 n 意义下是相同的，于是有

\prod_{i=1}^{\varphi(n)} r_i \equiv \prod_{i=1}^{\varphi(n)} (ar_i) \pmod{n}

即

\prod_{i=1}^{\varphi(n)} r_i \equiv a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} r_i \pmod{n}

每个 r_i 与 n 互素，所以 \prod_{i=1}^{\varphi(n)} r_i 也与 n 互素，故可约去，得

a^{\varphi(n)} \equiv 1 \pmod{n}

【定理】扩展欧拉定理

设 a, m 为正整数，b 为非负整数，则：

若 \gcd(a, m) = 1，则
a^b \equiv a^{b \bmod \varphi(m)} \pmod{m}
若 \gcd(a, m) \neq 1 且 b < \varphi(m)，则直接计算 a^b \pmod{m}
若 \gcd(a, m) \neq 1 且 b \geq \varphi(m)，则
a^b \equiv a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod{m}

Miller_Rabin

本章由 Furina_Aurora 编写。

【前置】素数判断

众所周知，我们判断一个数是否是素数，经常会用到以下代码：

inline bool isprime(int x){
    if(x<=1) return false;
    for(int i=2;i<x;i++){
        if(x%i==0) return false;
    }
    return true;
}

然而上方的代码在判断如 998244353 这样的大素数时，容易超时，所以对上方代码进行了一些改进：

inline bool isprime(int x){
    if(x<=1) return false;
    for(int i=2;1LL*i*i<=x;i++){
        if(x%i==0) return false;
    }
    return true;
}

然而，你认为这还是太慢了，于是你引进了欧拉筛（伪代码）：

int LinearSieve(int n){
    memset(is_prime,true,sizeof is_prime);
    is_prime[0]=is_prime[1]=false;
    int tot=0;
    for(int i=2;i<=n;i++){
        if(is_prime[i])primes[tot++]=i;
        for(int j=0;j<tot;j++){
            if(1LL*primes[j]*i>n)break;
            is_prime[primes[j]*i]=false;
            if(i%primes[j]==0)break;
        }
    }
    return tot;
}

那么除了上述的判断方式，有没有更快的方法呢？

有的有的，那就是 Miller-Rabin 素数测试！

【原理与定义】

Miller-Rabin 基于费马小定理实现，这个算法大致是这样的：

取一个序列 a，满足 1\le a_1,a_2,a_3,\cdots,a_k<n，然后把它们作为定理中的 a 代入到费马小定理中看看定理是否成立，如果检验不成立，则 n 为合数；如果检验成立，不能直接断定 n 为素数。Miller-Rabin 还需要检查连续平方过程中是否出现 -1，属于强伪素数测试。采用常数时间模乘时，k 轮测试需要 \mathcal O(k \log n) 次模乘。

【例题】SP288

这是 Miller-Rabin 的模板题，这里我们给出代码。

:::success[代码]{open}

#include<bits/stdc++.h>
#define int long long
using namespace std;

int prime[]={2,325,9375,28178,450775,9780504,1795265022};

// 省略快读

inline int mul(int x,int y,int MOD){
    return (unsigned __int128)(unsigned long long)x*(unsigned long long)y%MOD;
}

inline int qpow(int x,int y,int MOD){
    int res=1;
    while(y){
        if(y&1)res=mul(res,x,MOD);
        x=mul(x,x,MOD);
        y>>=1;
    }
    return res;
}

inline bool Miller_Rabin(int n,int a){
    int d=n-1,r=0;
    while(!(d&1))d>>=1,r++;
    int z=qpow(a,d,n);
    if(z==1)return true;
    for(int i=0;i<r;i++){
        if(z==n-1)return true;
        z=mul(z,z,n);
    }
    return false;
}

inline bool isprime(int n){
    if(n<=1)return false;
    for(int i=0;i<7;i++){
        if(n==prime[i])return true;
        if(prime[i]%n==0)continue;
        if(!Miller_Rabin(n,prime[i]%n))return false;
    }
    return true;
}

inline void solve(){
    int n=read();
    if(isprime(n))cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
}

signed main(){
    int T=read();
    while(T--)solve();
    return 0;
}

:::

Pollard-Rho

本章由 Stellar_River 编写。

【定义】

设 n 是待分解合数，p 是 n 的某个素因子，且保证 p\leq \sqrt n。

选取伪随机映射

f(x)=(x^2+c)\bmod n\quad c\neq0,-2

从随机初值 x_0 出发迭代生成序列

x_{k+1}=f(x_k)

:::info[生日悖论带来的关键观察]{open}

序列在模 n 下进入循环的期望长度为 \mathcal O(\sqrt n)；
序列在模 p 下进入循环的期望长度仅为 \mathcal O(\sqrt p)\leq\mathcal O(n^{\frac14})。

当序列在模 p 下重合、但在模 n 下尚未重合时，即

x_i\equiv x_j\pmod p\quad\quad x_i\not\equiv x_j\pmod n

则

p\mid |x_i-x_j|

但

n\nmid |x_i-x_j|

于是

d=\gcd(|x_i-x_j|,n)

此时给出 n 的一个非平凡因子，且满足 1<d<n；实际迭代也可能得到 d=1 或 d=n，分别需要继续迭代或重新尝试。

【\text{Floyd} 检测】

举一个生动的 🐢🐇 赛跑的问题。

不必存储整个序列，用双指针同时走：

每对 (x,y) 计算 d=\gcd(|x−y|,n)。若 1<d<n 即命中；若 d=n 说明选 c 不当导致模 n 也重合，换 c 重试。

威尔逊定理

本章由 Furina_Aurora 编写。

【定义】

对于整数 n\ge 2，n 是素数当且仅当 (n-1)!\equiv -1 \ (\bmod \ n)

【证明】

这里证明同余式成立时 n 必为素数的方向。 :::success[反证]{open} 我们不妨假设 n 为合数，取真因子 d，满足 1<d<n，则 d\le n-1，故 d\mid (n-1)!，即 (n−1)! \equiv 0 \ (\bmod \ d)

又由假设 (n−1)! \equiv −1 \ (\bmod \ n) 两边模 d 得，(n−1)! \equiv −1 \ (\bmod \ d)

然而 0\equiv -1 \ (\bmod \ d)，与假设矛盾。

所以，n 没有真因子，是素数，得证。

反过来，若 n=p 为素数，则模 p 的非零剩余类中，除 1 和 p-1 外，其余元素均可与不同于自身的逆元配对，每对乘积为 1。因此 (p-1)!\equiv 1\cdot(p-1)\equiv-1\pmod p；p=2 时也成立。
### 【推论】半阶乘平方公式
对于奇素数 p，公式如下：
((p-1)/2)!^2\equiv (-1)^{(p+1)/2} \ (\bmod p)
举个例子：

当 p=7 时，(3!)^2=36\equiv 1

【推论】广义威尔逊

公式如下：原公式不构成有效的数学命题，故暂不列出。

【推论】威尔逊商公式

\text{W}(p)=((p-1)!+1)/p\in \Z

【推论】威尔逊素数

满足 p^2 \mid (p−1)!+1 的素数 p 称威尔逊素数，目前已知 5,13 和 563。

莫比乌斯函数

本章由 Furina_Aurora 编写。

【积性函数】

我们设 f(n) 满足以下条件：

f(1)=1
在正整数 a,b 互素条件下，f(ab)=f(a) \times f(b)

那么我们称这个函数 f(n) 为积性函数，如果对于任意的 a,b 条件均成立，则称，这个函数为完全积性函数。

【狄利克雷卷积】

定义两个函数 f 和 g 的狄利克雷卷积为：

h(n)=\sum_{d\mid n}f(d)\times g(\frac{n}{d})

【定义】

莫比乌斯函数 \mu(n) 是积性函数，其定义如下：

若 n=1，则 \mu(1)=1
若存在素数 p 使得 p^2\mid n，则 \mu(n)=0
若 n 没有平方因子，且 n 是 p 个质数的乘积，则 \mu(n)=(-1)^p

【性质】

若 n=1，则 \sum_{d \mid n} \mu(d)=1
否则，\sum_{d\mid n}\mu(d)=0

:::success[证明]{open} 若 n=1，n 仅有约数 d=1，且 \mu(1)=1，结论成立。

不妨设 n>1，分解 n 得：

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

其中 k\geq 1，p_i 两两不同。由 \mu 得定义得，\mu(d)\ne 0 当且仅当 d 无平方因子

又 \because d\mid n

\therefore d=\prod_{i\in S}p_i$ 且 $S\subseteq \{ 1,2,\dots,k\}

且此时 \mu{d}=(-1)^{|S|}，所以

\sum_{d\mid n}\mu(d)=\sum_{S\subseteq\{ 1,2,\dots k\}}(-1)^{|S|}=\sum^{k}_{r=0}\binom{k}{r}(-1)^r

由二项式定理得，

\sum^{k}_{r=0}\binom{k}{r}(-1)^r=(1-1)^k=0

得证。

注：由人工证明，但使用了 DeepSeek V4 整理证明过程。
## 莫比乌斯反演
本章由 Furina_Aurora 编写。
### 【定义】
我们设 f 和 g 两个函数，由定理得：如果对于任意正整数 x 满足
g(x)=\sum_{d\mid x}f(d)
则有：
f(x)=\sum_{d\mid x}\mu(\frac{x}{d})\times g(d)

:::success[证明]{open} 将 g(d)=\sum_{e\mid d}f(e) 带入等式右端得，

\sum_{d\mid x}\mu\!\left(\frac{x}{d}\right)g(d)=\sum_{d\mid x}\mu\!\left(\frac{x}{d}\right)\sum_{e\mid d}f(e)\tag{1}

因 x 只有有限多个约数，上方的式子是有限双重和，故交换求和次序得

\sum_{d\mid x}\mu\!\left(\frac{x}{d}\right)\sum_{e\mid d}f(e)=\sum_{e\mid x}f(e)\sum_{\substack{d\mid x\\ e\mid d}}\mu\!\left(\frac{x}{d}\right)\tag{2}

我们固定 e，令 d=e\times t，条件 e\mid d\mid x 等价于 t\mid \frac{x}{e}，且 d\mapsto t 是一一对应的，则有

\sum_{\substack{d\mid x\\ e\mid d}}\mu\!\left(\frac{x}{d}\right)=\sum_{t\mid x/e}\mu\!\left(\frac{x}{et}\right)=\sum_{t\mid x/e}\mu\!\left(\frac{x/e}{t}\right).\tag{3}

我们记 m=\frac{x}{e}，注意到 t\mapsto\dfrac{m}{t} 把 m 得约数集合 \{ t:t\mid m\} 双射到自身，故

\sum_{t\mid m}\mu\!\left(\frac{m}{t}\right)=\sum_{t\mid m}\mu(t)

上方得式子等于 1 或 0，而 m=\frac{x}{e}=1 当且仅当 e=x，合并 (1)(2)(3) 得：

\begin{cases}1,&e=x,\\[2pt]0,&e<x,\end{cases}=f(x).

证毕。

注：由人工证明，但使用了 DeepSeek V4 整理证明过程。

【例题】P3455

感谢 DanseSolo 的建议，采用这道题作例题。

莫比乌斯反演板子题喵~

简化题意：求 \sum_{i=1}^{a}\sum_{j=1}^{b}\llbracket\gcd(i,j)=d\rrbracket 的值，这个式子等同于 \sum_{i=1}^{\lfloor\frac{a}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{b}{d}\rfloor}\llbracket\gcd(i,j)=1\rrbracket。

代码就不放了。

浅谈数学（二）

前言

往期回顾

编写人员

扩展欧几里得

【前置】裴蜀定理

【例题】

欧拉函数

【定义】

【性质】

【例题】GCD

【证明】欧拉定理

【定理】扩展欧拉定理

Miller_Rabin

【前置】素数判断

【原理与定义】

【例题】SP288

Pollard-Rho

【定义】

【\text{Floyd} 检测】

威尔逊定理

【定义】

【证明】

【推论】广义威尔逊

【推论】 威尔逊商公式

【推论】威尔逊素数

莫比乌斯函数

【积性函数】

【狄利克雷卷积】

【定义】

【性质】

【例题】P3455

【推论】威尔逊商公式