$最大公因数(GCD)$&$最小公倍数定义(LCM)$

最大公因数定义：两个或多个整数共有的最大正整数因数
最小公倍数定义：两个或多个整数的最小的正整数公倍数

$程序实现:$

$GCD$

//GCD
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
    //这里用三目运算符，其实就是if的简写版
}//方法叫辗转相除法

$LCM$方法1

//LCM #1
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}//配合GCD

$LCM$方法2

//LCM #2
int lcm(int a,int b){
	int i;
	for(i=max(a,b);;i++){
		if(i%a==0&&i%b==0){
			break;
		}
	}
	return i;
}

也是非常简单易上手

下一步,实战例题

例题来自$洛谷$

$题目传送门$

B3634 最大公约数和最小公倍数

题目描述

给定两个正整数 $a,b$，求他们的最大公约数（gcd）和最小公倍数（lcm）。这两个整数 $a,b$ 均在 int 范围内。

输入格式

两个整数 $a$ 和 $b$，用空格分隔。

输出格式

两个整数表示答案，用空格隔开。

输入输出样例 #1

输入 #1

6 15

输出 #1

3 30

分析

题目跟常规一样，只要2个数求最大公约数和最小公倍数
套用上面的函数，不多说上代码

#include <iostream>
using namespace std;
#define int long long
//把int的转换为long long
//建议这样用,注意main要换成signed
int gcd(int a,int b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}//最大公因数 
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}//最小公倍数
signed main(){
	int x,y;
	cin>>x>>y;
	cout <<gcd(x,y)<<' '<<lcm(x,y);
	return 0;
}

GCD和LCM的应用

• 约分:用$GCD$化简分子分母
• 通分:用$LCM$找到共同分母

这里附GCD和LCM的关系

$GCD(a,b)\times LCM(a,b)=|a\times b|$
有时候可以用到，利用一方的关系求另一方

~ $完结撒花$ ~

附：第一次发布8/20
文章第二次修改9/12
推荐$洛谷$作为你的刷题区域
下一篇预告:队列