数学--数论--最小公倍数+最大公约数

2020-11-06 00:50:32 浏览数 (1)

数学中约定： GCD（a，b)为a ,b的最大公因数 LCM（a，b）为小公倍数

必须要知道的公式:

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

先说GCD怎么求：

代码语言：javascript复制

int gcd(int a,int b){
	return __gcd(a,b); //不是我闹着玩，是真有这个函数
}

正经的来了，欧几里得算法

代码语言：javascript复制

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

if-else 比较慢，三目运算符优化：

代码语言：javascript复制

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

肯定不会爆栈，再给一种非递归算法：

代码语言：javascript复制

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

接下来就是最小公倍数了： LCM（a，b）=a∗b/GCD（a,b)

但是要是a*b爆了 long long咋整？

我们使用数学交换律大法：

L C M ( a , b ) = a / G C D ( a , b ) ∗ b LCM(a,b)=a /GCD(a,b)*bLCM(a,b)=a/GCD(a,b)∗b

因为 GCD一定是a或b的因子，所以上面的等式成立。

0 人点赞