热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

最大公约数(GCD)

题目描述求整数a、b的最大公约数。题目分析所谓求整数a、b的最大公约数,就是求同时满足a%c0、b%c0的最大正整数c,即求能够同时整除a和b的最大正整数c。暴力枚举若a、b均

题目描述

求整数a、b的最大公约数。

题目分析

所谓求整数a、b的最大公约数,就是求同时满足a%c=0、b%c=0的最大正整数c,即求能够同时整除a和b的最大正整数c。

暴力枚举

若a、b均不为0,则依次遍历不大于a(或b)的所有正整数,依次试验它是否同时满足两式,并在所有满足两式的正整数中挑选最大的那个即为所求;

若a、b其中有一个为0,那么最大公约数即为a、b中非零的那个;

若a、b均为0,则最大公约数不存在(任意数均可同时整除它们)。

说明:当a和b数值较大时(如100000000),该算法耗时较多。

欧几里德算法(又称辗转相除法)

若a、b全为0,则它们的最大公约数不存在;若a、b其中之一为0,则它们的最大公约数为非0的那个;若a、b都不为0,则使新a=b;新b=a%b然后重复该过程。

说明:证明过程见最下边。

代码实现

 
递归实现
#include 
using namespace std;

int gcd(int a, int b)
{
	if (a == 0 && b == 0)
		return -1; // 不存在

	// a、b为负数时,先求绝对值,再求最大公约数
	if (a <0)
		a = -a;
	if (b <0)
		b = -b;

	if (b == 0)
		return a;
	return gcd(b, a%b);
}

int main()
{
	int m, n;
	while (cin >> m >> n)
	{
		cout < 
循环实现
#include 
using namespace std;

int gcd(int a, int b)
{
	if (a == 0 && b == 0)
		return -1; // 不存在

	// a、b为负数时,先求绝对值,再求最大公约数
	if (a <0)
		a = -a;
	if (b <0)
		b = -b;

	while (b != 0)
	{
		int t = a%b;
		a = b;
		b = t;
	}
	return a;
}

int main()
{
	int m, n;
	while (cin >> m >> n)
	{
		cout < 

欧几里德算法证明

1> 证明a、b的公约数同时也是b、a mod b 的公约数

image

2> 证明若g是a、b的最大公约数,它同样也是b、a mod b 的最大公约数

我们假设g是a、b的最大公约数,但它并不是b、a mod b 的最大公约数,

image


推荐阅读
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • 本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符,并提供了多种编程语言的实现示例。 ... [详细]
  • 本文介绍两道有趣的编程问题:一是寻找给定数字n的连续数字序列及其个数,二是模拟一个翻杯子的游戏。同时附带一道智商题供读者思考。 ... [详细]
  • 采用IKE方式建立IPsec安全隧道
    一、【组网和实验环境】按如上的接口ip先作配置,再作ipsec的相关配置,配置文本见文章最后本文实验采用的交换机是H3C模拟器,下载地址如 ... [详细]
  • 本题探讨了在大数据结构背景下,如何通过整体二分和CDQ分治等高级算法优化处理复杂的时间序列问题。题目设定包括节点数量、查询次数和权重限制,并详细分析了解决方案中的关键步骤。 ... [详细]
  • JSOI2010 蔬菜庆典:树结构中的无限大权值问题
    本文探讨了 JSOI2010 的蔬菜庆典问题,主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性,提出了有效的解决方案,并详细解释了算法的实现过程。 ... [详细]
  • 本题来自WC2014,题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系,要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]
  • 本文探讨了如何通过预处理器开关选择不同的类实现,并解决在特定情况下遇到的链接器错误。 ... [详细]
  • 题目描述:给定一个N*M的网格,初始时网格中有k个芯片,每个芯片的位置已知。玩家可以在每一步操作中将所有芯片沿同一方向移动一格。如果芯片到达边界,则保持不动。目标是通过一系列操作,使每个芯片依次访问指定的目标位置。 ... [详细]
  • 本题要求实现一个函数,用于检查给定的字符串是否为回文。回文是指正向和反向读取都相同的字符串。例如,“XYZYX”和“xyzzyx”都是回文。 ... [详细]
  • Linux环境下C语言实现定时向文件写入当前时间
    本文介绍如何在Linux系统中使用C语言编程,实现在每秒钟向指定文件中写入当前时间戳。通过此示例,读者可以了解基本的文件操作、时间处理以及循环控制。 ... [详细]
  • 在高并发需求的C++项目中,我们最初选择了JsonCpp进行JSON解析和序列化。然而,在处理大数据量时,JsonCpp频繁抛出异常,尤其是在多线程环境下问题更为突出。通过分析发现,旧版本的JsonCpp存在多线程安全性和性能瓶颈。经过评估,我们最终选择了RapidJSON作为替代方案,并实现了显著的性能提升。 ... [详细]
  • 深入解析Spring启动过程
    本文详细介绍了Spring框架的启动流程,帮助开发者理解其内部机制。通过具体示例和代码片段,解释了Bean定义、工厂类、读取器以及条件评估等关键概念,使读者能够更全面地掌握Spring的初始化过程。 ... [详细]
  • Python 工具推荐 | PyHubWeekly 第二十一期:提升命令行体验的五大工具
    本期 PyHubWeekly 为大家精选了 GitHub 上五个优秀的 Python 工具,涵盖金融数据可视化、终端美化、国际化支持、图像增强和远程 Shell 环境配置。欢迎关注并参与项目。 ... [详细]
author-avatar
韦小娇900_433
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有