讲师中心 微信公众号
AI工具推荐 视频效率加速

C++怎么求最大公约数_C++中辗转相除法实现【解析】

落静姑娘_3831

落静姑娘_3831

发布时间:2026-03-13 15:04:03

|

813人浏览过

|

来源于php中文网

原创

C++17起可用std::gcd,需包含<numeric>并指定-std=c++17;参数为0时行为未定义;手写应取abs防负数,用迭代避免栈溢出,模板化支持long long等类型。

c++怎么求最大公约数_c++中辗转相除法实现【解析】

std::gcd 在 C++17 里直接用,但得开标准

如果你用的是 C++17 或更新(比如 GCC 7+、Clang 6+、MSVC 2017 Update 5+),std::gcd 已经是标准库函数,不用自己写。但它不在 <iostream> 里,得包含 <numeric>,而且编译时要明确指定标准:

  • g++ -std=c++17 main.cpp(不加 -std 默认可能是 C++14,std::gcd 就报错:‘gcd’ is not a member of ‘std’)
  • 返回值类型是参数类型的公共类型(比如 int 和 long 传进去,返回 long)
  • 两个参数都为 0 时行为未定义——实际运行可能抛异常或返回 0,别这么调用

手写辗转相除法要注意负数和零

经典递归/迭代写法看似简单,但 C++ 里 % 是取余(remainder),不是数学上的模(modulo)。负数参与运算时结果符号依赖被除数,容易让 gcd(-8, 12) 算出负值或死循环:

  • 安全做法是先取绝对值:abs(a) 和 abs(b) 再进算法
  • 边界检查不能只写 b == 0,得处理 a == 0 && b == 0 的情况(按定义应返回 0,但很多实现会崩溃)
  • 迭代版比递归更稳,避免栈溢出(尤其大数场景)
int gcd(int a, int b) {
    a = abs(a); b = abs(b);
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

unsigned 类型下 % 更干净,但没法输负数

如果业务确定输入非负(比如数组长度、内存块大小),用 unsigned int 能省掉 abs,且 % 行为完全确定:

C++14
C++14

C++14 对 C++11 的修正与增强版本,适合旧系统维护和较老工具链兼容。

下载
  • unsigned 下 a % b 永远 ≥ 0,不会出现负余数干扰逻辑
  • 但一旦传入负数,会触发静默整型提升成大正数(比如 -1 变成 4294967295),结果完全不可控
  • 接口设计时建议显式用 int + abs,比靠文档“约定不传负数”更可靠

模板版本支持 long long 和自定义整型

标准 std::gcd 是函数模板,能推导 long long、int128_t(GCC 扩展)等;自己写的也要考虑泛化:

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

  • 别硬写 int,用 typename T + static_assert(std::is_integral_v<T>)
  • std::gcd 对 long long 安全,但手写时若用 int 中间变量存余数,可能溢出(比如 LLONG_MAX % 2 还是大数,但塞进 int 就截断)
  • 如果项目禁用 STL 或需兼容旧编译器,推荐抄 libstdc++ 的实现:用 __gcd(GCC 内部函数,非标准但稳定)
C++ 求 GCD 看似一行代码的事,真正上线时卡住你的往往是编译标准、负数处理、类型宽度这三处——特别是混合使用 int 和 long long 参数时,连 std::gcd 都可能隐式转换出错。

热门AI工具

更多
咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

二狗PPT
二狗PPT Hot

一款AI演示文稿工具,主要用于专为中式职场打造的AI PPT生成工具,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

相关专题

更多
string转int
string转int

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

6179

2023.08.02

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

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

3005

2024.08.29

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

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

3868

2025.08.29

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

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

2685

2025.08.29

硬盘接口类型介绍
硬盘接口类型介绍

硬盘接口类型有IDE、SATA、SCSI、Fibre Channel、USB、eSATA、mSATA、PCIe等等。详细介绍:1、IDE接口是一种并行接口,主要用于连接硬盘和光驱等设备,它主要有两种类型:ATA和ATAPI,IDE接口已经逐渐被SATA接口;2、SATA接口是一种串行接口,相较于IDE接口,它具有更高的传输速度、更低的功耗和更小的体积;3、SCSI接口等等。

3128

2023.10.19

PHP接口编写教程
PHP接口编写教程

本专题整合了PHP接口编写教程,阅读专题下面的文章了解更多详细内容。

4809

2025.10.17

php8.4实现接口限流的教程
php8.4实现接口限流的教程

PHP8.4本身不内置限流功能,需借助Redis(令牌桶)或Swoole(漏桶)实现;文件锁因I/O瓶颈、无跨机共享、秒级精度等缺陷不适用高并发场景。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

3769

2025.12.29

java接口相关教程
java接口相关教程

本专题整合了java接口相关内容,阅读专题下面的文章了解更多详细内容。

446

2026.01.19

OpenJDK JVM参数怎么调优
OpenJDK JVM参数怎么调优

Java应用运行缓慢,如何调整JVM参数?本专题介绍OpenJDK JVM性能调优的基本流程,涵盖性能指标确认、运行数据采集、内存配置和垃圾回收分析,帮助你先定位瓶颈,再通过对照测试验证效果,避免直接套用参数而影响应用稳定性。

0

2026.10.16

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Core Guidelines
C++ Core Guidelines

共0课时 | 0人学习

C++ Reference
C++ Reference

共0课时 | 0人学习

C++ 官方标准说明
C++ 官方标准说明

共0课时 | 0人学习

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

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn