最大公因数原理：
(1) 36=24+12
(2) 24=12*2+0
(3) 12=0+12
在第三步中发现b==0，然后返回a，即上一步的b，上上步的a%b
#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 gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(int argc, char const *argv[]) {
printf("%d\n",gcd(24,16));
return 0;
}
最小公倍数原理：
a*b/gcd(a,b)
#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 lcm(int a,int b){
return a/gcd(a,b)*b; // a*b可能溢出，所以需要先除个gcd(a,b)
}
int main(int argc, char const *argv[]) {
cout<<lcm(24,16);
return 0;
}
