最大公约数

一、辗转相除法
1，循环除

#include <iostream>
using namespace std;
int main(){
    int a,b,t;
    cin>>a>>b;
    if(a<b)swap(a,b);
    do{
        t=a%b;
        a=b;
        b=t;
    }while(t);
    cout<<a<<endl;
    return 0;
}

2，迭代除

#include <iostream>
using namespace std;
int gcd(int a,int b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

int main(){
    int a,b,t;
    cin>>a>>b;
    if(a<b)swap(a,b);
    cout<< gcd(a,b)<<endl;
    return 0;
}

扩展：a,b最小公倍数=(ab最大公约数^2)a/最大公约数b/最大公约数=a*b/最大公约数