专栏首页开心的学习之路最大公约数和最小公倍数

最大公约数和最小公倍数

       辗转相除法(欧几里得算法)算是求最大公约数最简单高效的算法了,这几行代码用最简洁的方式写了这个算法,值得牢牢记住:

#include <cstdio>

//最大公约数 

int Gcd(int a, int b)
{
	return b == 0 ? a : Gcd(b, a%b); 
}

//最小公倍数

int Lcm(int a, int b)
{
	return a / Gcd(a, b) * b; 
} 

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	int gcd = Gcd(a, b);
	printf("%d与%d的最大公约数为%d\n", a, b, gcd);
	int lcm = Lcm(a, b);
	printf("%d与%d的最小公倍数为%d\n", a, b, lcm);
	return 0;
}

       既然采用了递归,自然会想到会不会栈溢出,有人证明出,Gcd函数的递归层数不会超过4.785lgN + 1.6723(N = max(a,b))。

求最小公倍数可以用lcm = a*b / gcd,为了防止a*b过大溢出,常采用先除以最大公约数再乘以b的方式。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础练习 阶乘计算

      n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A[0]表示a的个位,A[1]表示a的十位,依次类推...

    刘开心_1266679
  • 基础练习 数列排序

      第一行为一个整数n。   第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    刘开心_1266679
  • 基础练习 字母图形

    ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC

    刘开心_1266679
  • AGC015 C Nuske vs Phantom Thnook(前缀和)

    attack
  • HDU-5575-Discover Water Tank

    ACM模版 描述 ? 题解 左偏树可解。 初始默认所有 z=0z = 0 的情况,然后枚举 z=1z = 1 的情况来更新答案,并且可以用并查集来维护合并的水箱...

    f_zyj
  • ex_gcd(个人模版)

    ex_gcd: 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 in...

    Angel_Kitty
  • hihoCoder 1700 相似颜色

            题目链接: http://hihocoder.com/problemset/problem/1700

    Ch_Zaqdt
  • 复习C艹(更新中)

    之前在win7中运行c/c++下个vc就可以编译运行了,现在换了Mac,上网一看需要下个xcode,哎哟,好大啊,当时又没网,捉急,咦,mac的终端可以编译cp...

    仇诺伊
  • 短视频APP制作,设置高斯模糊

    yunbaokeji柯基
  • HDU4035 Maze(期望DP)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack

扫码关注云+社区

领取腾讯云代金券