数论3——gcd&&lcm

gcd(a, b)，就是求a和b的最大公约数

lcm(a, b)，就是求a和b的最小公倍数

然后有个公式

a*b = gcd * lcm ( gcd就是gcd(a, b)， ( •̀∀•́ ) 简写你懂吗)

解释（不想看就跳过）{

　　首先，求一个gcd，然后。。。

　　a / gcd 和 b / gcd 这两个数互质了，也就是 gcd( a / gcd ，b / gcd ) = 1，然后。。。

　　lcm = gcd * (a / gcd) * (b / gcd)

　　lcm = (a * b) / gcd

　　所以。。a*b = gcd * lcm

}

所以要求lcm，先求gcd

辣么，问题来了，gcd怎么求

辗转相除法

while循环

LL gcd(LL a, LL b){
    LL t;
    while(b){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

还有一个递归写法

LL gcd(LL a, LL b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

LL gcd(LL a, LL b){
    return b ? gcd(b, a%b) : a;
}
//两种都可以

辣么，lcm = a * b / gcd

(注意，这样写法有可能会错，因为a * b可能因为太大超出int 或者超出 longlong)

所以推荐写成： lcm = a / gcd * b

然后几个公式自己证明一下

gcd(ka, kb) = k * gcd(a, b)

lcm(ka, kb) = k * lcm(a, b)

上次做题碰到这个公式

lcm(S/a, S/b) = S/gcd(a, b)

S = 9，a = 4，b = 6，小数不会lcm，只好保留分数形式去通分约分。

当我看到右边那个公式。。。。

(╯°Д°)╯┻━┻

这TM我怎么想的到，给我证明倒是会证。 T_T

【附录】

这里给出使用欧几里得算法求最大公约数的递归和非递归的程序，同时给出穷举法求最大公约数的程序。

从计算时间上看，递推法计算速度最快。

程序中包含条件编译语句用于统计分析计算复杂度。

/*
 * 计算两个数的最大公约数三种算法程序
 */

#include <stdio.h>

//#define DEBUG
#ifdef DEBUG
int c1=0, c2=0, c3=0;
#endif

int gcd1(int, int);
int gcd2(int, int);
int gcd3(int, int);

int main(void)
{
    int m=42, n=140;

    printf("gcd1: %d %d result=%d
", m, n, gcd1(m, n));
    printf("gcd2: %d %d result=%d
", m, n, gcd2(m, n));
    printf("gcd3: %d %d result=%d
", m, n, gcd3(m, n));
#ifdef DEBUG
    printf("c1=%d  c2=%d  c3=%d
", c1, c2, c3);
#endif

    return 0;
}

/* 递归法：欧几里得算法，计算最大公约数 */
int gcd1(int m, int n)
{
#ifdef DEBUG
    c1++;
#endif
    return (m==0)?n:gcd1(n%m, m);
}

/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd2(int m, int n)
{
    while(m>0)
    {
#ifdef DEBUG
    c2++;
#endif
        int c = n % m;
        n = m;
        m = c;
    }
    return n;
}

/* 连续整数试探算法，计算最大公约数 */
int gcd3(int m, int n)
{
    if(m>n) {
        int temp = m;
        m = n;
        n = temp;
    }
    int t = m;
    while(m%t || n%t)
    {
#ifdef DEBUG
    c3++;
#endif
        t--;
    }
    return t;
}

View Code

关键代码（正解）：

/* 迭代法（递推法）：欧几里得算法，计算最大公约数 */
int gcd(int m, int n)
{
    while(m>0)
    {
        int c = n % m;
        n = m;
        m = c;
    }
    return n;
}