大约在去年的时候我发了一篇关于最大公因数和最小公倍数的文章
最小公倍数和最大公约数如何求(函数)
当时我只在里面讲了辗转相除和暴力两种方法,一个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
m
a
x
(
a
,
b
)
)
O(\log_2 {max(a,b)})
O(log2max(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
×
b
=
g
c
d
(
a
,
b
)
×
l
c
m
(
a
,
b
)
a \times b=gcd(a,b) \times lcm(a,b)
a×b=gcd(a,b)×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),太不稳定啦!
最小公倍数我也不用多说了
好了,就这么多,如果又没说到的打击可以补充