求最大公约数与最小公倍数

求最大公约数与最小公约数

求最大公约数（辗转相除法||二进制）和最小公倍数
辗转相除法：
1.求t=a%b；
2.if(t!=0) m=n,n=t,重复1（调用子程序）；
3.if(t==0) 终止子程序；
4.输出此时b值；
二进制法：（适合高精度）
1.终止条件：gcd(a,a)=a;(a==b)
2.关系式：
case a < b :gcd(a,b)=gcd(b,a);
case 同偶 ：gcd(a,b)=2*gcd(a/2,b/2);
case a偶b奇 ：gcd(a,b)=gcd(a/2,b);
case a奇b偶 ：gcd(a,b)=gcd(a,b/2);
case a奇b偶 ：gcd(a,b)=gcd(a,b-a);

code：

#include<cstdio>
using namespace std;
int gcd(int a,int b){    //辗转相除法
//    if(a%b==0)  return b;
//    else   return gcd(b,a%b);

    return !b?a:gcd(b,a%b);

}
int lcm(int a,int b){
    return a*b/gcd(a,b);    //最小公倍数乘最大公约数等于它们的乘积
}
int main(){
    int a,b,t;
    scanf("%d%d",&a,&b);

//    if(a<b)   {t=a;a=b;b=t;}

    t=gcd(a,b);
    printf("%d %d",t,a*b/t);
    return 0;
}

二进制（适合高精）：

#include<cstdio>
using namespace std;
int gcd(int a,int b){
    if(a==b) return a;      //递归终止条件
    if(a<b) return gcd(b,a);
    if(a&1){
        if(b&1) return 2*gcd(a>>1,b>>1);
        else return gcd(a>>1,b);
    }
    else{
        if(b&1) return gcd(a,b>>1);
        else return gcd(b,a-b);
    }
}
int lcm(int a,int b){
    return a*b/gcd(a,b);    //最小公倍数乘最大公约数等于它们的乘积
}
int main(){
    int a,b,t;
    scanf("%d%d",&a,&b);
    t=gcd(a,b);
    printf("%d %d",t,a*b/t);
    return 0;
}