数学问题-最大公约数和最小公倍数

最大公约数

理论

1 递归式：gcd(a,b)=gcd(b,a%b)
2 递归边界：gcd(a,0)=a
注：0和任意一个整数a的最大公约数都是a

代码

#include <iostream>
using namespace std;
int gcd(int a, int b){
	if(b==0)return a;		
	return gcd(b, a%b);
} 
int main(int argc,char * argv[]){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",gcd(a,b));
	return 0;
} 

最小公倍数

理论

1 求最大公约数d
2 最小公倍数为a/d*b
注：
1 因为d是最大公约数，所以a一定可以被d整除
2 不可写为a*b/d，因为ab有可能溢出

代码

#include <iostream>
using namespace std;
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;
} 
int main(int argc,char * argv[]){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",lcm(a,b));
	return 0;
}