ACM基础之最大公约数、最小公倍数

最大公约数Greatest Common Divisor(GCD)

// 用于swap()
#include <iostream>
using namespace std;int GCD(int a, int b)
{
    if (a < b){
    swap(a, b);}while (a % b != 0){
    int temp;temp = a % b;a = b;b = temp; //当a%b=0时，b是最大公约数}return b;
}

推荐：

// 用于swap()
#include <iostream>
using namespace std;int Division(int a, int b)
{
    if (a < b){
    swap(a, b); //a要大于等于b}while (b != 0){
    int temp;temp = a % b;a = b;b = temp; //当a%b=0时，a是最大公约数，b是相除到0}return a;
}

Least Common Multiple
最小公倍数=原数a*原数b/最小公约数。

// 用于swap()
#include <iostream>
using namespace std;int GCD(int a, int b)
{
    if (a < b){
    swap(a, b); //a要大于等于b}while (b != 0){
    int temp;temp = a % b;a = b;b = temp; //当a%b=0时，a是最大公约数，b是相除到0}return a;
}int LCM(int a, int b)
{
    return a * b / GCD(a, b);
}