专栏文章

浅谈数论

LLoyal_Soldier
算法·理论参与者 18已保存评论 21

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
21 条
当前快照
1 份
快照标识符
@miob29jv
此快照首次捕获于
2025/12/02 16:17
3 个月前
此快照最后确认于
2025/12/02 16:17
3 个月前
查看原文
由于本人是 xxs，数学学的不多，文章有错误还请多多谅解。
本文同步发布于博客。

质数

质数，也称素数。
若一个数 pp 为质数，则它的因数只有 1,p1, p。
例如 2,32, 3 都是质数。
特别的，11 不是质数。

判断质数

判断一个数 pp 是否是质数，需要判断 2∼p2\sim \sqrt p 是否有数是 pp 的因数，若有，则说明 pp 有除了 1,p1, p 以外的因数，pp 不是质数，否则，pp 是质数。
时间复杂度 O(p)O(\sqrt p)。
CPP
bool is_prime(int p)
{
	if(p == 1) return false;//特判，1 不是质数
	for(int i = 2;i * i <= p;i ++)
		if(p % i == 0) return false;//判断 p 是否有除了 1,p 以外的因数，如果有，p 不是质数
	return true;//如果 p 只有 1,p 两个因数，p 是质数
}

质数筛

埃氏筛

埃氏筛，全称埃拉托斯特尼筛法。
埃氏筛的核心思想是：如果一个数 pp 是质数，那么 pp 的倍数的不是质数，即将所有质数的倍数都标记为合数，不需要标记合数的倍数。
埃氏筛时间复杂度 O(nlog⁡log⁡n)O(n \log \log n)，但是会重复标记（例如 66 被 2,32, 3 分别标记了一次），导致常数较大。
CPP
bool is_prime[N];//is_prime[i] 用来标记 i 是不是质数 
void sieve_primes(int n)
{
	for(int i = 1;i <= n;i ++) is_prime[i] = true;//初始化 
	is_prime[1] = false;//1 不是质数 
	for(int i = 2;i <= n;i ++)
	{
		if(is_prime[i] == false) continue;//因为只标记质数的倍数，所以遇到合数要跳过 
		for(int j = i * 2;j <= n;j += i)
			is_prime[j] = false;//标记 
	}
}

欧拉筛

欧拉筛，也称线性筛，是一种比埃氏筛更优秀的筛法。
欧拉筛的核心思想是：对于每个合数，只会被它的最小质因数给筛掉，从而避免重复标记。
欧拉筛需要多维护一个数组 primeprime，primeiprime_i 表示第 ii 个质数。
欧拉筛需要用当前遍历到的 ii 和当前筛出的质数 primejprime_j 标记合数，因为 i×primeji\times prime_j 一定是合数，先进行标记，然后，最重要的优化来了：如果 i mod primej=0i\bmod prime_j = 0，说明 ii 的最小质因数为 primejprime_j，此时应该停止标记。
欧拉筛的时间复杂度为 O(n)O(n)。
CPP
bool is_prime[N];//is_prime[i] 用来标记 i 是不是质数 
int prime[N], tot;//tot 表示当前质数的个数，prime[i] 表示第 i 个质数 
void sieve_primes(int n)
{
	for(int i = 1;i <= n;i ++) is_prime[i] = true;//初始化 
	is_prime[1] = false;//1 不是质数 
	for(int i = 2;i <= n;i ++)
	{
		if(is_prime[i] == true) prime[++ tot] = i;//如果第 i 个数是质数，把它加入 prime 数组 
		for(int j = 1;j <= tot && prime[j] * i <= n;j ++)
		{
			is_prime[prime[j] * i] = false;//标记 
			if(i % prime[j] == 0) break;//当 prime[j] 是 i 的最小质因数是，停止标记 
		}
	}
}

整除与同余

整除

设 aa 是非零整数，bb 是整数。若存在一个整数 xx，使得 b=a×xb = a\times x，那么称 bb 可被 aa 整除 或 aa 可以 整除 bb，记作 a∣ba\mid b，也可以说 bb 是 aa 的倍数或 aa 是 bb 的因数。例如 2∣6,4∣82 \mid 6,4\mid 8。
整除具有以下性质：
  • 性质 11：如果 a∣ba\mid b 并且 b∣cb\mid c，那么 a∣ca\mid c
  • 性质 22：a∣ba\mid b 并且 b∣cb\mid c 等价于 a∣(b×x+c×y)a\mid (b\times x + c\times y)
  • 性质 33：设 m≠0m\ne 0，那么 a∣ba\mid b 等价于 (m×a)∣(m×b)(m\times a)\mid (m\times b)
  • 性质 44：设整数 xx 和 yy 满足 a×x+b×y=1a\times x + b\times y = 1，且 a∣n,b∣na\mid n,b\mid n，那么 a×b∣na\times b\mid n
    • 证明：
      • 根据性质 33 可得 a×b∣b×na\times b\mid b\times n 且 a×b∣a×na\times b\mid a\times n
      • 再根据性质 22 可得 a×b∣a×n×x+b×n×ya\times b\mid a\times n\times x + b\times n\times y
      • 其中 a×n×x+b×n×y=n×(a×x+b×y)=n×1=na\times n\times x + b\times n\times y = n\times(a\times x + b\times y) = n\times 1 = n，所以 a×b∣na\times b\mid n
  • 性质 55：若 b=q×d+cb = q\times d + c，那么 d∣bd\mid b 的充要条件是 d∣cd\mid c

同余

若 a,ba,b 为两个整数，且他们的差 a−ba - b 能被某个自然数 pp 整除，则称 aa 和 bb 关于模 pp 同余，记作 a≡b(modp)a\equiv b \pmod p，意味着 a−b=p×ka - b = p \times k（kk 为某个整数）。例如 36≡1(mod5)36\equiv 1 \pmod 5，此时 36−1=35=5×736 - 1 = 35 = 5\times 7。
对于整数 a,b,ca,b,c 和自然数 n,mn,m，对模 mm 同余具有以下性质：
  • 自反性：a≡a(modm)a\equiv a \pmod m
  • 对称性：若 a≡b(modm)a\equiv b \pmod m，则 b≡a(modm)b\equiv a \pmod m
  • 传递性：若 a≡b(modm),b≡c(modm)a\equiv b \pmod m,b\equiv c \pmod m，则 a≡c(modm)a\equiv c \pmod m
  • 同加性：若 a≡b(modm)a\equiv b \pmod m，则 a+n≡b+n(modm)a + n\equiv b + n \pmod m
  • 同乘性：若 a≡b(modm)a\equiv b \pmod m，则 a×n≡b×n(modm)a \times n\equiv b \times n \pmod m。若 a≡b(modm),c≡d(modm)a\equiv b \pmod m,c\equiv d \pmod m，则 a×c≡b×d(modm)a\times c\equiv b\times d \pmod m
  • 同幂性：若 a≡b(modm)a\equiv b \pmod m，则 an≡bn(modm)a^n \equiv b^n \pmod m
要注意的是，同余不满足同除性，即不满足 a÷n≡b÷n(modm)a\div n\equiv b\div n \pmod m。

最大公约数

最大公约数指两个整数 a,ba,b 公有的因数中最大的数，记作 gcd⁡(a,b)\gcd(a,b)。

辗转相除法

辗转相除法用来求两个数的最大公约数，又称欧几里得算法，其核心为：gcd⁡(x,y)=gcd⁡(y,x mod y)\gcd(x,y) = \gcd(y, x\bmod y)。
证明：
  • 若 x<yx < y，则 gcd⁡(y,x mod y)=gcd⁡(y,x)=gcd⁡(x,y)\gcd(y, x\bmod y) = \gcd(y, x) = \gcd(x,y)。
  • 若 x≥yx\ge y，设 x=q×y+rx = q\times y + r，其中 0≤r<y0\le r < y，显然 r=x mod yr = x\bmod y。对于 x,yx,y 的任意公约数 dd，因为 d∣x,d∣q×yd\mid x,d\mid q\times y，所以 d∣(x−q×y)d\mid (x - q\times y)，即为 d∣rd\mid r，因此 dd 为 y,ry, r 的公约数。
辗转相除法的流程如下：
  • 若 y=0y = 0，则说明答案为 xx。
  • 若 y≠0y\ne 0，则根据 gcd⁡(x,y)=gcd⁡(y,x mod y)\gcd(x, y) = \gcd(y, x\bmod y) 往下递归。
时间复杂度 O(log⁡max⁡(x,y))O(\log \max(x,y))。
CPP
int gcd(int x, int y)
{
	if(y == 0) return x;//y = 0 则返回答案 
	return gcd(y, x % y);//否则继续递归 
}

最小公倍数

最小公倍数指两个整数 a,ba,b 公有的倍数中最小的数，记作 lcm(a,b)\text{lcm}(a,b)。
定理：x×y=gcd⁡(x,y)×lcm(x,y)x\times y = \gcd(x, y) \times \text{lcm}(x, y)。
根据以上定理，可以得出 lcm(x,y)=x×y÷gcd⁡(x,y)\text{lcm}(x, y) = x\times y\div \gcd(x, y)。
用辗转相除法求出 gcd⁡(x,y)\gcd(x, y) 然后直接计算就行了，时间复杂度与辗转相除法一样。
CPP
int gcd(int x, int y)
{
	if(y == 0) return x;
	return gcd(y, x % y);
}
int lcm(int x, int y)
{
	return x * y / gcd(x, y);
}

欧拉定理

若正整数 a,na, n 互质，则：
aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1\pmod n
其中 φ(n)\varphi(n) 为欧拉函数，表示 1∼n1\sim n 中与 nn 互质的数的个数。

证明

设 x1,x2,…,xφ(n)x_1,x_2,\dots,x_{\varphi(n)} 为 1∼n1\sim n 中与 nn 互质的数。
这时，我们发现 a×x1,a×x2,…,a×xφ(n)a\times x_1, a\times x_2, \dots, a\times x_{\varphi(n)} 具有这个性质：每个数  mod n\bmod n 两两不同，且余数与 nn 互质。而且，x1,x2,…,xφ(n)x_1, x_2, \dots, x_{\varphi(n)} 也具有这个性质。
有了这个性质，将 a×x1,a×x2,…,a×xφ(n)a\times x_1, a\times x_2, \dots, a\times x_{\varphi(n)} 都  mod n\bmod n 后一定是 φ(n)\varphi(n) 个不同的与 nn 互质的数，那么：
x1×x2×⋯×xφ(n)≡a×x1×a×x2×⋯×a×xφ(n)(modn)1≡aφ(n)(modn)x_1\times x_2\times \dots\times x_{\varphi(n)}\equiv a\times x_1\times a\times x_2\times \dots\times a\times x_{\varphi(n)}\pmod n\\ 1\equiv a^{\varphi(n)}\pmod n

费马小定理

若整数 pp 为质数且 pp 与整数 aa 互质，则满足：
ap−1≡1(modp)a^{p - 1}\equiv 1\pmod p

证明

因为 pp 是质数，那么 φ(p)=p−1\varphi(p) = p - 1，这时就转化成了欧拉定理的一种情况，由于满足欧拉定理，费马小定理一定成立。

裴蜀定理

对于二元一次不定方程 a×x+b×y=ca\times x + b\times y = c，有解当且仅当 gcd⁡(a,b)∣c\gcd(a, b)\mid c。

证明

设 d=gcd⁡(a,b)d = \gcd(a, b)，显然 d∣a,d∣bd\mid a, d\mid b。
则 d∣a×x,d∣b×yd\mid a\times x, d\mid b\times y。
那么，要使方程成立，必须满足 d∣cd\mid c。

扩展欧几里得算法

扩展欧几里得算法是用来求解 a×x+b×y=gcd⁡(a,b)a\times x + b\times y = \gcd(a, b) 的一种算法。
首先，根据数论中的相关定理，此方程一定有解。
因为 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a\bmod b)，所以 a×x+b×y=gcd⁡(a,b)=gcd⁡(b,a mod b)=x×b+y×(a mod b)=x×b+y×(a−⌊ab⌋×b)=y×a+(x−⌊ab⌋×y)×ba\times x + b\times y = \gcd(a, b) = \gcd(b, a\bmod b) = x \times b + y\times (a\bmod b)= x\times b + y\times (a - \lfloor \frac{a}{b} \rfloor \times b) = y\times a + (x - \lfloor \frac{a}{b} \rfloor \times y)\times b。
可以根据欧几里得算法递归，当 b=0b = 0 时，可以得出 x=1,y=0x = 1, y = 0,。
扩展欧几里得算法流程如下：
  • 当 b=0b = 0 时，x=1,y=0x = 1, y = 0。
  • b≠0b\ne 0，则往下递归计算 gcd⁡(b,a mod b)\gcd(b, a\bmod b)，得到一组解 x′,y′x',y'，根据以上的推论，x=y′,y=x′−⌊ab⌋×y′x = y',y = x' - \lfloor \frac{a}{b} \rfloor \times y'。
扩展欧几里得算法时间复杂度与欧几里得算法一样，为 O(log⁡max⁡(a,b))O(\log \max(a, b))
CPP
void exgcd(int a, int b)
{
	if(b == 0)
	{
		x = 1, y = 0;//b = 0 时，x = 1,y = 0
		return;
	}
	exgcd(b, a % b);//递归
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
}

逆元

若 a×x≡1(modp)a\times x\equiv 1\pmod p，并且 a,pa, p 互质，则称 aa 模 pp 的乘法逆元为 xx，记作 a−1a^{-1}。

费马小定理求逆元

注意，当模数 pp 是质数且 a≠0a\ne 0 时，才可使用费马小定理求逆元。
根据费马小定理：
ap−1≡1(modp)a^{p - 1}\equiv 1\pmod p
因此：
a×ap−2≡1(modp)a\times a^{p - 2}\equiv 1\pmod p\\
很明显，此时 ap−2a^{p - 2} 即为 a−1a^{-1}。
使用快速幂求出 ap−2 mod pa^{p - 2}\bmod p 即可，时间复杂度 O(log⁡p)O(\log p)。
CPP
int qpow(int a, int b, int mod)
{
	int ans = 1;
	while(b)
	{
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}//快速幂模板
int get_inv(int a, int p)
{
	return qpow(a, p - 2, p);//求出逆元
}

扩展欧几里得算法求逆元

a×x≡1(modp)a\times x\equiv 1 \pmod p 可以转化为求解 a×x+p×y=gcd⁡(a,p)=1a\times x + p\times y = \gcd(a, p) = 1（当 gcd⁡(a,p)=1\gcd(a, p) = 1 才有解，这也符合逆元的定义）。那么，可以使用扩展欧几里得算法求解。
但是，求解出来的 xx 可能是负数，需要通过累加 pp 来处理一下。
CPP
void exgcd(int a, int b)//扩展欧几里得算法模板
{
	if(b == 0)
	{
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b);
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
}
int get_inv(int a, int p)
{
	exgcd(a, p);
	return (x % p + p) % p;//使 x 变为最小正整数解
}

递推求逆元

设 p=k×i+r,r<i,1<i<pp = k\times i + r, r < i, 1 < i < p，然后把这个式子放在  mod p\bmod p 意义下可以得到：
k×i+r≡0(modp)k\times i + r \equiv 0\pmod p
将两边同时乘上 i−1i^{-1} 和 r−1r^{-1} 可以得到：
                     k×r−1+i−1≡0                                  (modp)                                       i−1≡−k×r−1                    (modp)                                       i−1≡−⌊pi⌋×(p mod  i)−1(modp)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k\times r^{-1} + i^{-1}\equiv 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod p\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv -k\times r ^ {-1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod p\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i^{-1}\equiv - \lfloor \frac{p}{i} \rfloor \times (p\bmod\ i)^{-1}\pmod p
通过这个式子即可从前面的数推出当前数的逆元。
CPP
void get_inv(int n, int p)
{
	inv[1] = 1;//初始值
	for(int i = 2;i <= n;i ++) inv[i] = (p - p / i) * inv[p % i] % p;//递推式
}

中国剩余定理

中国剩余定理用来求解以下同余方程组：
{x≡a1(modb1)x≡a2(modb2)…x≡an(modbn)\begin{cases} x\equiv a_1&\pmod {b_1}\\ x\equiv a_2&\pmod {b_2}\\ \dots\\ x\equiv a_n&\pmod {b_n} \end{cases}
其中 bib_i 两两互质。
根据余数的可加性，只有求出以下 nn 个方程组的解，则可以求出原方程的解：
{x1≡a1(modb1)x1≡0(modb2)…x1≡0(modbn){x2≡0(modb1)x2≡a2(modb2)…x2≡0(modbn)…{xn≡0(modb1)xn≡0(modb2)…xn≡an(modbn)\begin{cases} x_1\equiv a_1&\pmod {b_1}\\ x_1\equiv 0&\pmod {b_2}\\ \dots\\ x_1\equiv 0&\pmod {b_n} \end{cases} \begin{cases} x_2\equiv 0&\pmod {b_1}\\ x_2\equiv a_2&\pmod {b_2}\\ \dots\\ x_2\equiv 0&\pmod {b_n} \end{cases} \dots \begin{cases} x_n\equiv 0&\pmod {b_1}\\ x_n\equiv 0&\pmod {b_2}\\ \dots\\ x_n\equiv a_n&\pmod {b_n} \end{cases}
原方程解 x=∑i=1nxix = \sum^{n}_{i = 1} x_i。
设当前求解的方程组为第 cc 个：
{xc≡0(modb1)xc≡0(modb2)…xc≡ac(modbc)…xc≡0(modbn)\begin{cases} x_c\equiv 0&\pmod {b_1}\\ x_c\equiv 0&\pmod {b_2}\\ \dots\\ x_c\equiv a_c&\pmod {b_c}\\ \dots\\ x_c\equiv 0&\pmod {b_n} \end{cases}
将上方程组转化为：
{yc≡0(modb1)yc≡0(modb2)…yc≡1(modbc)…yc≡0(modbn)\begin{cases} y_c\equiv 0&\pmod {b_1}\\ y_c\equiv 0&\pmod {b_2}\\ \dots\\ y_c\equiv 1&\pmod {b_c}\\ \dots\\ y_c\equiv 0&\pmod {b_n} \end{cases}
那么，xc=yc×acx_c = y_c\times a_c。
由于 bib_i 两两互质，可得 yc mod ∏i=1nbibc=0y_c\bmod \frac{\prod_{i = 1}^{n} b_i}{b_c} = 0。设 ∏i=1nbibc\frac{\prod_{i = 1}^{n} b_i}{b_c} 为 lcl_c，则 bc=lc×wcb_c = l_c\times w_c。
根据以上方程组，可知 lc×wc≡1(modbc)l_c\times w_c\equiv 1\pmod {b_c}，显然 wcw_c 就是 lcl_c 的逆元，直接使用扩展欧几里得算法求就行了。
方程解 x=∑i=1nac×lc×lc−1x = \sum_{i = 1}^{n} a_c\times l_c\times l_c^{-1}。
由于需要求的是方程的最小正整数解，需要累加 ∏i=1nai\prod_{i = 1}^{n} a_i 并取模。
CPP
void exgcd(int a, int b)//扩展欧几里得算法模板
{
	if(b == 0)
	{
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b);
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
}
for(int i = 1;i <= n;i ++)
{
	int qwq = cj / a[i];//cj 为所有数的乘积，qwq 即为 l_c
	exgcd(qwq, a[i]);//求出逆元
	ans = (ans + qwq * b[i] * x) % cj;//ans 为最终答案
}
cout << (ans + cj) % cj;//转化成最小正整数解

欧拉函数

欧拉函数 φ(n)\varphi(n) 表示 1∼n1\sim n 中与 nn 互质的数的个数，特别的，φ(1)=1\varphi(1) = 1。
欧拉函数是一个积性函数，若 n⊥mn\perp m，则 φ(n×m)=φ(n)×φ(m)\varphi(n\times m) = \varphi(n)\times \varphi(m)。
设 nn 分解质因数后为 ∏i=1mpiqi\prod_{i = 1}^mp_i^{q_i}，则 φ(n)=n×∏i=1m(1−1pi)\varphi(n) = n\times \prod_{i = 1}^m (1 - \frac{1}{p_i})。

证明

  • 由于欧拉函数是一个积性函数，只需要考虑 piqip_i^{q_i} 的取值就能计算所有数的欧拉函数了。
  • 若一个数与 piqip_i^{q_i} 不互质，则这个数一定是 pip_i 的倍数，那么 1∼piqi1\sim p_i^{q_i} 中有 piqi−1p_i^{q_i - 1} 个数和 piqip_i^{q_i} 不互质，反过来和 piqip_i^{q_i} 互质的数的个数为 piqi−piqi−1=piqi×(1−1pi)p_i^{q_i} - p_i^{q_i - 1} = p_i^{q_i}\times (1 - \frac{1}{p_i})，则 φ(n)=n×∏i=1m(1−1pi)\varphi(n) = n\times \prod_{i = 1}^m (1 - \frac{1}{p_i})。
O(n)O(\sqrt n) 求解 φ(n)\varphi(n)：
CPP
phi = n;//phi 表示 phi(n)
for(int i = 2;i * i <= n;i ++)
    if(n % i == 0)
    {
        phi = phi / i * (i - 1);//乘上 (1 - 1 / p)
        while(n % i == 0) n /= i;//把 n 中的 i 全部筛去
    }
if(n != 1) phi = phi / n * (n - 1);
但是，以上算法如果计算多个数的欧拉函数，容易超时，需要使用欧拉筛优化，时间复杂度 O(n)O(n)：
CPP
phi[i] = 1;
for(int i = 2;i <= n;i ++)
{
	if(phi[i] == 0)
		p[++ tot] = i, phi[i] = i - 1;//若 i 是质数，则 phi(i) = i - 1
	for(int j = 1;j <= tot && i * p[j] <= n;j ++)
	{
		if(i % p[j] == 0)//i 与 p[j] 不互质的情况
		{
			phi[i * p[j]] = phi[i] * p[j];
			break;
		}
		else phi[i * p[j]] = phi[i] * (p[j] - 1);//i 与 p[j] 互质的情况
	}
}

评论

共 21 条评论，欢迎与作者交流。

正在加载评论...