0

0

C++怎么求最大公约数 C++中std::gcd和std::lcm【总结】

裘德小鎮的故事

裘德小鎮的故事

发布时间:2026-03-02 15:28:52

|

686人浏览过

|

来源于php中文网

原创

c++怎么求最大公约数 c++中std::gcd和std::lcm【总结】

std::gcd 在 C++17 中才可用,别在旧标准里找它

如果你用 g++ 编译时报错 ‘gcd’ is not a member of ‘std’,大概率是编译器没开 C++17 或更高标准。GCC 和 Clang 默认不启用 C++17,必须显式指定:-std=c++17-std=c++20。MSVC 2019 v16.10+ 默认支持,但老版本仍需确认。

常见错误现象:头文件写了 #include <numeric></numeric>,也用了 std::gcd(a, b),但链接失败或编译报错——不是漏头文件,是标准版本卡住了。

  • 检查方式:std::gcd 的声明在 <numeric></numeric> 中,但仅当 __cpp_lib_gcd_lcm >= 201606L 宏定义存在时才生效
  • 替代方案:C++11 及以前只能手写欧几里得算法,比如 while (b) { auto t = b; b = a % b; a = t; }
  • 注意:std::gcd(0, 0) 返回 0,符合数学定义,但部分手写实现会除零崩溃

std::gcd 要求两个参数同号,负数会出乎意料

std::gcd 对负数的处理是“取绝对值后计算”,但它的参数类型是整型模板(std::common_type_t<m n></m>),不自动转正。如果传入负数,结果仍是非负整数,但容易误判逻辑——比如你本想判断“是否互质”,却因符号问题漏掉边界情况。

使用场景:读取用户输入或解析文件得到的带符号整数,直接喂给 std::gcd 前没做清理。

立即学习C++免费学习笔记(深入)”;

Favird No-Code Tools
Favird No-Code Tools

无代码工具的聚合器

下载
  • std::gcd(-12, 8) 返回 4,和 std::gcd(12, 8) 一样
  • std::gcd(-12, -8) 同样返回 4
  • std::gcd(0, -5) 返回 5,而有人可能预期是 -5(实际不会,标准规定结果 ≥ 0)
  • 安全做法:显式取绝对值,如 std::gcd(std::abs(a), std::abs(b)),避免依赖隐式行为

std::lcm 的溢出风险比 gcd 高得多,尤其大数相乘

std::lcm(a, b) 内部等价于 std::abs(a) / std::gcd(a, b) * std::abs(b),但乘法发生在除法之后——如果中间结果溢出,整个表达式就 UB(未定义行为)。而 std::gcd 只涉及取模,数值只减不增。

性能影响:std::lcm 多一次除法和一次乘法,但主要瓶颈不在运算本身,而在溢出检测缺失。

  • std::lcm(2000000000, 1999999999)int 上大概率溢出,即使最终结果能存进 long long
  • 没有内置的溢出检查机制,也不会抛异常,结果是静默错误
  • 若需安全 lcm,建议先转成 long long 再调用:std::lcm(static_cast<long long>(a), static_cast<long long>(b))</long></long>
  • 或者手动检查:先算 g = std::gcd(a, b),再判断 abs(a)/g 是否超过 LLONG_MAX / abs(b)

Windows MinGW 和某些 libc++ 版本对 std::lcm 支持不完整

MinGW-w64 的旧版 libstdc++(如 GCC 9.2 之前)实现了 std::gcd,但没实现 std::lcm;Clang + libc++ 12 之前也缺少 std::lcm。这时即使加了 -std=c++17#include <numeric></numeric> 也不含 std::lcm 声明。

兼容性影响:跨平台项目在 Linux(GCC 10+)能跑,在 Windows(MinGW GCC 8)直接编译不过。

  • 检查方法:预编译宏 __cpp_lib_lcm 应 ≥ 201606L,否则不保证存在
  • 可加编译期断言:static_assert(__cpp_lib_lcm >= 201606L, "std::lcm not available");
  • 稳妥做法:自己封装一个 fallback lcm,用 std::gcd + 类型提升 + 溢出防护
  • 别依赖 IDE 的头文件跳转——它可能显示声明,但链接时找不到符号

事情说清了就结束。最常被忽略的是:std::gcdstd::lcm 看似简单,但标准版本、符号处理、溢出路径、平台实现这四点,任一出错都会导致静默错误或编译失败,且难以定位。

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
while的用法
while的用法

while的用法是“while 条件: 代码块”,条件是一个表达式,当条件为真时,执行代码块,然后再次判断条件是否为真,如果为真则继续执行代码块,直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容,供大家免费下载体验。

104

2023.09.25

string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

910

2023.08.02

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

596

2024.08.29

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

294

2025.08.29

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

210

2025.08.29

windows查看端口占用情况
windows查看端口占用情况

Windows端口可以认为是计算机与外界通讯交流的出入口。逻辑意义上的端口一般是指TCP/IP协议中的端口,端口号的范围从0到65535,比如用于浏览网页服务的80端口,用于FTP服务的21端口等等。怎么查看windows端口占用情况呢?php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

1356

2023.07.26

查看端口占用情况windows
查看端口占用情况windows

端口占用是指与端口关联的软件占用端口而使得其他应用程序无法使用这些端口,端口占用问题是计算机系统编程领域的一个常见问题,端口占用的根本原因可能是操作系统的一些错误,服务器也可能会出现端口占用问题。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

1159

2023.07.27

windows照片无法显示
windows照片无法显示

当我们尝试打开一张图片时,可能会出现一个错误提示,提示说"Windows照片查看器无法显示此图片,因为计算机上的可用内存不足",本专题为大家提供windows照片无法显示相关的文章,帮助大家解决该问题。

827

2023.08.01

Golang 测试体系与代码质量保障:工程级可靠性建设
Golang 测试体系与代码质量保障:工程级可靠性建设

Go语言测试体系与代码质量保障聚焦于构建工程级可靠性系统。本专题深入解析Go的测试工具链(如go test)、单元测试、集成测试及端到端测试实践,结合代码覆盖率分析、静态代码扫描(如go vet)和动态分析工具,建立全链路质量监控机制。通过自动化测试框架、持续集成(CI)流水线配置及代码审查规范,实现测试用例管理、缺陷追踪与质量门禁控制,确保代码健壮性与可维护性,为高可靠性工程系统提供质量保障。

45

2026.02.28

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C# 教程
C# 教程

共94课时 | 10.5万人学习

C 教程
C 教程

共75课时 | 5.1万人学习

C++教程
C++教程

共115课时 | 20.2万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号