最大公因数和最小公倍数函数（补续）

本文主要是介绍最大公因数和最小公倍数函数（补续），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大约在去年的时候我发了一篇关于最大公因数和最小公倍数的文章
最小公倍数和最大公约数如何求（函数）
当时我只在里面讲了辗转相除和暴力两种方法，一个O(logn),一个O(n),现在我又带着新的方法回来了（v-v ）

递归

递归的话肯定就是要用递归函数了，我们令gcd（a,b）为a和b 的最大公因数
那么可以写出以下递归式

return gcd(b,a%b);

其原理呢就是辗转相除，那什么时候止呢？我们在用辗转相除的时候怎么弄就怎么弄，辗转相除是 b == 0 时停， 那我们也就 b == 0 时停，辗转相除是返回a我们也返回 。所以可得以下代码

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

总结一下，本质上是 辗转相除，只不过用了递归，时间复杂度仍为
$$O({\log }_{2}max(a,b))$$
小贴士：（为了我们方便敲最大公因数函数，我们是一直在缩减，所以，再给大家看看更简便的，编译器自带）

#include<bits/stdc++.h>
using namespace std;
int main()
{int a,b;cin>>a>>b;cout<<__gcd(a,b);return 0;
}

当然不好看的话可以这样

#include<bits/stdc++.h>
#define gcd __gcd
using namespace std;
int main()
{int a,b;cin>>a>>b;cout<<gcd(a,b);return 0;
}

好的，最大公因数搞定了，下面是最小公倍数，
其实最小公倍数很简单，你知道最大公因数，就能知道最小公倍数，因为
$$a\times b=gcd(a,b)\times lcm(a,b)$$
所以最小公倍数就是ab/gcd(a,b),这里就不给予证明了，大家可以上网搜搜

辗转相减法

顾名思义，就是用减法，怎么减呢？
一个一个减啦，每次最大的减最小的，如果a==b就直接返回了
代码如下

int gcd(int a,int b){if(a==b) return a;th+=1;return a>b?gcd(a-b,b):gcd(a,b-a); //三元组//如果a>b就a-b否则b-a
}

辗转相减的时间复杂度最坏是O(min(a,b)),最好是O(1),太不稳定啦！
最小公倍数我也不用多说了
好了，就这么多，如果又没说到的打击可以补充

这篇关于最大公因数和最小公倍数函数（补续）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---