题目描述

1、最大公约数代码

（1）辗转相除法

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,t;
    cin>>a>>b;
    if(b>a)swap(a,b); 
    while(1){
    t=a%b
    if(t==0)break;
        a=b;b=t;
    }
    cout<<b;
}

（2）__gcd(x,y);
int、long long类型都可以，需要注意的是两个类型必须要相同，还有不能用浮点型，当然手写gcd函数也是可以的，它头文件是algorithm。

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int a,b;

    cin>>a>>b;

    cout<<__gcd(a,b)<<endl;

    return 0;

}

（3）常规法（容易超时）

#include<bits/stdc++.h>
using namespace std;
int main(){
   int a,b;
   cin>>a>>b;
   for(int i=min(a,b);i>=1;i--){
    if(a%i==0&&b%i==0){
        cout<<i;
        break;
       }
   }
    return 0;
}

2、最小公倍数

（1）正常思路
最小公倍数就是能被这两个数同时整除的最小的数，那么运用循环进行遍历不断试除找到这个数。

#include<bits/stdc++.h>
using namespace std;
int main(){
   int a,b;
   cin>>a>>b;
   for(int i=max(a,b);i<=a*b;i++){
    if(i%a==0&&i%b==0){
        cout<<i;
        break;
       }
   }
    return 0;
}

（2）辗转相除法

最小公倍数=两个数相乘除最大公约数。
最大公约数则用辗转相除法求出。

 #include<bits/stdc++.h>
using namespace std;
int main(){
   int a,b;
   cin>>a>>b;
   int k=__gcd(a,b);
   cout<<a*b/k; 
    return 0;
}

（3）利用 k/m=i k/n=j
k=mi 则mi/n=j 所以当mi能整除n时mi为最小公倍数

#include<stdio.h>

int main()

{

int m, n,i=1;

scanf("%d%d", &m, &n);

while (m * i%n != 0)

{

i++;

 }

printf("%d", m * i);

    return 0;

}