测试用例 Synchnorized installation proxy routing gulp vue状态管理 郑州小程序公司 河南普通话考试报名 matlab中log函数 sallenkey滤波器 linux 获取系统时间 kafka消费不到数据 dwf文件怎么转成dwg 安装python mysql事务 python语言 python自学入门 python的lambda函数 javaindexof java程序 java生成当前时间 java数组 java中collection java接口调用 销售单打印软件 微信超级好友 批处理if 微信公众号点餐系统 pr抖动特效 java表白代码 网页自动点击 深入解析windows操作系统 粉碎文件工具 德玛上单天赋 一键清除锁屏密码 脚本文件 ps取色 ae怎么复制图层 ps白色背景变透明
当前位置: 首页 > 学习教程  > 编程语言

最大公约数和最小公倍数(附加更易懂的欧几里得算法(辗转相除法)及其定理证明)1818 最大公约数和1984 最大公约数 2135 最小公倍数

2020/12/5 10:05:00 文章标签:

每日刷题&#xff08;八十四&#xff09; 1818 最大公约数题目描述 输入两个正整数&#xff0c;求其最大公约数。 详细C代码如下&#xff1a; #include<cstdio>int gcd(int a, int b) {if(b 0)return a;else return gcd(b, a % b); } int main() {int m, n;while(sc…

每日刷题(八十四)

1818 最大公约数题目描述

输入两个正整数,求其最大公约数。
在这里插入图片描述
详细C++代码如下:

#include<cstdio>

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

int main()
{
	int m, n;
	while(scanf("%d%d", &m, &n) != EOF)
		printf("%d\n", gcd(m, n));
	return 0;
}

运行结果如下:
在这里插入图片描述按Ctrl + Z然后回车可以跳出EOF循环

或者代码写成这样也可

#include<bits/stdc++.h>
using namespace std;

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

int main()
{
	int m, n;
	while(cin >> m >> n)
	cout << gcd(m, n) << endl;
	return 0;
}

欧几里得算法基于下面定理:

在这里插入图片描述
在这里插入图片描述
Attention!!!
0和任意一个整数a的最大公约数都是a

因此我们可以得到
1、递归式:gcd(a, b) = gcd(b, a % b)
2、递归边界:gcd(a, 0) = a

可以写成

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

更简洁的写法为

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

1984 最大公约数题目描述

读入n个正整数,求出这n个数的最小值、最大值以及它们两的最大公约数,并输出。输入中第一行为n,接下来为n个大于零的整数。
在这里插入图片描述
详细C++代码如下:

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	int n;
	while(cin >> n)
	{
		int a[n];
		for(int i = 0; i < n; i++)
		{
			cin >> a[i]; 
		} 
		sort(a, a + n);
		int MAX = a[n - 1];
		int MIN = a[0];
		cout << MIN << " " << MAX << " " << gcd(MAX, MIN) << endl;
	}
	
	return 0;
} 

运行结果如下:
在这里插入图片描述

2135: 最小公倍数题目描述

给定两个正整数,计算这两个数的最小公倍数。
在这里插入图片描述
详细C++代码如下:

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
	return a / gcd(a, b) * b;
}

int main()
{
	int m, n;
	while(cin >> m >> n)
	{
		cout << lcm(m, n) << endl;
	}
	return 0;
}

运行结果如下:
在这里插入图片描述

最小公倍数相关知识要素

最小公倍数求解是建立在最大公约数d基础上,a和b的最小公倍数 = a * b / d
在这里插入图片描述
由于a * b可能溢出,所以更恰当的写法是 a / d * b

之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!


本文链接: http://www.dtmao.cc/news_show_450141.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?