GCD和LCM

　　GCD _ LCM 是给你两个数A B 的最大公约数，以及最小公倍数

　　the greatest common divisor and the least common multiply !

　　最大公约数最简单、最常见的算法，就是辗转相除法 :

假设 GCD(A , B) ; A / B = P ; A % B = Q; 那么 A = B P + Q;

　　GCD(B, Q);

　　GCD (A , B) % GCD (B , Q) = 0 : 因为 A 的表达式当中包括了 B 、 Q；

　　同理，我们可以由： Q = A - BP;

　　GCD (B , Q) % GCD (A , B) = 0;

　　所以说两者相等，得到了辗转相除法求得GCD 的方法，那么 LCM 如何求得呢？？

　　通过A B 的乘法因子来看： GCD 是相同的因子， LCM 是相同的因子只是取一个，

两个想乘，刚刚好可以互补，即 GCD * LCM = A*B;

　　所以说最大公约数可以通过最小公倍数来求得！

　　那么代码！！：：：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <queue>

#include <list>

#include <map>

#include <stack>

#include <set>

using namespace std;

int GCD(int a, int b){

    if(b == )  return a;

    else return GCD(b, a % b);

}

int main()

{

    cout << "Hello world!" << endl;

    printf("GCD :  %d , LCM : %d \n", GCD(, ),  *  / GCD(, ));

    printf("GCD :  %d , LCM : %d \n", GCD(, ),  *  / GCD(, ));

    printf("GCD :  %d , LCM : %d \n", GCD(, ),  *  / GCD(, ));

    return ;

}

　　但是有些时候，我们需要注意，使用 long long int , 防止部分题目进行卡数据，注意题目中的数据范围

巴特西

GCD和LCM

最新文章

热门文章