当前位置: 首页 > news >正文

OI 数论 1

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. ab 均为偶数 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. ab 均为奇数 gcd(a, b) = gcd(a - b, b) 奇数减奇数得偶数,缩小数值(后续可按规则 2/3 处理)

三、关键优化点

  1. 避免取模:用“移位”替代“除以 2”,用“减法”替代“大整数取模”,降低计算开销;
  2. 规模缩减快:每次迭代至少将其中一个数减半(或减为差值),时间复杂度与欧几里得算法相当,均为 O(log(min(a, b)))
  3. 兼容性强:支持包含 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);}
}

迭代法实现扩展欧几里得算法

一、基础迭代推导

QQ20251012-202820

图片1

图片来自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;
}
http://www.hskmm.com/?act=detail&tid=29563

相关文章:

  • 2.4 DQN 变体(Rainbow)
  • Emacs折腾日记(三十二)——org mode的基本美化
  • 2025 工业风机十大品牌全景解析报告:覆盖离心风机,防爆风机,矿用风机的最新推荐
  • 2.3 深度 Q 网络(Deep Q-Network, DQN)
  • Linux存储媒介devmount
  • Linux系统目录(文件)结构
  • 实用指南:如何读懂Mach-O:构建macOS和iOS应用安全的第一道认知防线
  • vim配置使用
  • shell高级
  • shell流程控制
  • shell展开shell数组
  • shell排错
  • 原木
  • 格式化输出与文本处理
  • 2025年10月镀锌卷板厂家最新推荐排行榜,有花镀锌卷板,无花镀锌卷板,高锌层镀锌卷板,批发镀锌卷板公司推荐
  • React 19.2 重磅更新!这几个新特性终于来了
  • Akka.NET高性能分布式Actor框架完全指南
  • 基于Docker搭建MySQL Cluster
  • 2025 年抗氧剂厂家最新推荐排行榜,聚酯防黄变抗氧剂,透明膜防晶点抗氧剂,PC聚碳防黄变抗氧剂公司推荐!
  • PaddleX服务化部署精度低于命令行调用的原因及解决方案 - 指南
  • 某中心与华盛顿大学公布机器人研究奖项与学者名单
  • 会话跟踪方案
  • 阻塞、非阻塞、同步、异步的区别是什么?
  • 如何防范员工泄露数据给 AI?2025年选型与落地实战版
  • Linux文本编辑三剑客之grep
  • Linux文本编辑三剑客之sed
  • 做了项目经理才发现:上台发言,其实都有套路
  • 占位符
  • 什么是IO多路复用?
  • 进程、线程和协程之间的区别和联系