gcd 与 ex_gcd 的 C++ 实现
1. 最大公约数(GCD)
1.1 定义
最大公约数(Greatest Common Divisor)指两个或多个整数共有约数中最大的一个,记为 gcd(a, b)。对于非负整数 a 和 b,gcd(a, b) 是能同时整除 a 和 b 的最大正整数。
1.2 欧几里得算法(辗转相除法)
核心原理基于数学公式:gcd(x, y) = gcd(y, x % y)
(其中 a % b 表示 a 除以 b 的余数)
终止条件:当 y = 0 时,gcd(x, 0) = x
递归实现
// 递归计算 gcd(x, y)
int gcd(int x, int y) {if (y == 0) return x; // 如果 那么返回yelse return gcd(y, x % y);
}
小优化 快速幂 & gcd
// 假设 p 为全局模数(快速幂运算的取模参数)
int p;// 快速幂函数:计算 (x^y) % p
int f_pow(int x, int y) {int ans = 1; // 结果初始化为 1(任何数的0次幂为1)x %= p; // 底数先取模,防止初始值过大while (y > 0) { // 指数大于0时循环(二进制分解思想)if (y % 2 == 1) { // 若当前指数为奇数,将当前底数乘入结果ans = (ans * x) % p; // 结果取模,避免溢出}x = (x * x) % p; // 底数平方(对应指数二进制右移一位)y /= 2; // 指数除以2(二进制右移)}return ans; // 返回 (x^y) % p 的结果
}// 融合快速幂的 GCD 计算(递归版)
// 注意:此处为特殊场景设计,非标准 GCD 逻辑,需根据具体需求调整
int gcd(int x, int y) {// 终止条件:若 x 能被 y 整除,则 y 是最大公约数if (x % y == 0) {return y;} else {// 递归计算:在求余过程中嵌入快速幂(示例逻辑,需根据实际场景修改)// 这里用 x 对 y 取余后,将余数作为指数计算 y 的幂,再参与 GCD 递归int rem = x % y; // 计算 x 除以 y 的余数int pow_val = f_pow(y, rem); // 计算 y^rem % p(快速幂应用)return gcd(y, pow_val % y); // 用幂运算结果的余数继续递归求 GCD}
}
Stein 算法(二进制最大公约数算法)笔记
一、Stein 算法简介
Stein 算法是计算两个非负整数最大公约数(gcd) 的高效算法,由 J. Stein 于 1967 年提出。
它的核心优势是避免欧几里得算法中的大整数取模运算,转而通过二进制位操作(移位、与、减) 实现,在计算机处理大整数时效率更高(尤其适合硬件实现,减少除法/取模的高开销)。
二、核心原理(基于二进制特性)
Stein 算法的推导依赖整数的二进制性质,核心规则围绕“偶数/奇数”分类处理,递归或迭代地缩小问题规模,最终得到 GCD。
设需计算 gcd(a, b)
(约定 a ≥ b ≥ 0
,若不满足则交换),核心规则如下:
条件 | 处理逻辑 | 原理说明 |
---|---|---|
1. b = 0 |
终止,返回 a |
任何数与 0 的 gcd 是其本身(gcd(a, 0) = a ) |
2. a 和 b 均为偶数 |
gcd(a, b) = 2 * gcd(a >> 1, b >> 1) |
偶数可提取公因子 2,`a >> 1 (右移 1 位) |
3. a 为偶数,b 为奇数 |
gcd(a, b) = gcd(a >> 1, b) |
偶数的公因子 2 与奇数无关,仅需对偶数减半 |
4. a 为奇数,b 为偶数 |
gcd(a, b) = gcd(a, b >> 1) |
同规则 3,对偶数减半 |
5. a 和 b 均为奇数 |
gcd(a, b) = gcd(a - b, b) |
奇数减奇数得偶数,缩小数值(后续可按规则 2/3 处理) |
三、关键优化点
- 避免取模:用“移位”替代“除以 2”,用“减法”替代“大整数取模”,降低计算开销;
- 规模缩减快:每次迭代至少将其中一个数减半(或减为差值),时间复杂度与欧几里得算法相当,均为
O(log(min(a, b)))
; - 兼容性强:支持包含 0 的输入(如
gcd(0, x) = x
),也可通过取绝对值扩展到负整数。
四、C++ 实现(递归 + 迭代版)
4.1 递归实现(直观体现原理)
#include <bits/stdc++.h>
using namespace std;
// Stein 算法递归版:计算 a 和 b 的最大公约数
int stein_gcd(int a, int b) {// 步骤1:处理负数(转为非负,gcd 与符号无关)a = abs(a), b = abs(b);// 步骤2:终止条件(b = 0 时,gcd 为 a)if (b == 0) {return a;}// 步骤3:确保 a ≥ b(简化后续判断,避免重复处理)if (a < b) {swap(a, b);}// 步骤4:判断 a、b 的奇偶性,按规则处理if ((a & 1) == 0 && (b & 1) == 0) {// 规则2:a和b均为偶数(a&1 == 0 表示偶数)return 2 * stein_gcd(a >> 1, b >> 1);} else if ((a & 1) == 0 && (b & 1) == 1) {// 规则3:a偶、b奇return stein_gcd(a >> 1, b);} else if ((a & 1) == 1 && (b & 1) == 0) {// 规则4:a奇、b偶return stein_gcd(a, b >> 1);} else {// 规则5:a和b均为奇数(a - b 为偶数,缩小规模)return stein_gcd(a - b, b);}
}
迭代法实现扩展欧几里得算法
一、基础迭代推导
图片来自OiWiki
代码实现(基础迭代版)
int gcd(int a, int b, int& x, int& y) {x = 1, y = 0;int x1 = 0, y1 = 1, a1 = a, b1 = b;while (b1) {int q = a1 / b1;tie(x, x1) = make_tuple(x1, x - q * x1);tie(y, y1) = make_tuple(y1, y - q * y1);tie(a1, b1) = make_tuple(b1, a1 - q * b1);}return a1;
}