秒懂算法 │数论之GCD和LCM

简介: 本篇内容介绍了GCD和LCM的多种编码方法及其典型例题。

640.jpg

01、GCD定义

整数a和b的最大公因数是指能同时整除a和b的最大整数,记为gcd(a, b)。

例如:gcd(15, 81) = 3,gcd(0, 44) = 44,gcd(0, 0) = 0,gcd(-6, -15) = 3,gcd(-17,289) = 17。

注意:由于-a的因子和a的因子相同,因此gcd(a, b) = gcd(|a|, |b|)。编码时只需要关注正整数的最大公因数。

02、GCD性质

(1)gcd(a,b) = gcd(a, a+b) = gcd(a, ka+b)

(2)gcd(ka, kb) = k·gcd(a, b)

(3)定义多个整数的最大公约数:gcd(a, b, c) = gcd(gcd(a, b), c)

(4)若gcd(a, b) = d,则gcd(a/d, b/d) = 1,即a/d与b/d互素。这个定理很重要。

(5)gcd(a+cb, b) = gcd(a, b)

03、GCD编码

编程时可以直接用c++函数std::__gcd(a, b)。注意:参数a和b都应该是正整数,否则可能会返回负数。

下面介绍三种算法。

3.1 欧几里得算法

用辗转相除法求gcd,即gcd(a, b) = gcd(b, a mod b)。代码是:

int gcd(int a, int b){  // 一般要求a>=0, b>0。若a=b=0,代码也正确,返回0
    return b? gcd(b, a%b):a;
}

这是竞赛中最常用的编码,它极为高效,“拉梅定理”给出了复杂度分析。

拉梅定理:用欧几里得算法计算两个正整数的最大公因数,需要的除法次数不会超过两个整数中较小的那个十进制数的位数的5倍。

推论:用欧几里得算法求gcd(a, b),a > b,需要次位运算。
欧几里得算法的缺点是需要

image.png

做取模运算,而高精度的除法取模比较耗时,此时可以用“更相减损术”,它只用到了减法。

3.2 更相减损术

计算基于这一性质:gcd(a, b) = gcd(b, a-b) = gcd(a, a-b)。

[欧几里得《几何原本》是公元前三世纪的著作,中国《九章算术》成于公元一世纪,流行本是三世纪刘徽的注本,都非常古老。]

计算步骤:用较大的数减较小的数,把所得的差与较小的数比较,然后继续做减法操作,直到减数和差相等为止。

编码也很简单:

int gcd(int a, int b){
   while(a != b){
       if(a > b)  a = a - b;
       else       b = b - a;
   }
   return a;
}

更相减损术虽然避免了欧几里得的取模计算,但是计算次数比欧几里得算法多很多,极端情况下需要计算

image.png

次,例如a = 100,b = 1时,需计算100次。

3.3 Stein算法

它是更相减损术的改进,用位运算进行了优化。这里不做解析,请自己了解。

读者可以用下面这一题练习高精度大数的计算和Stein算法,类似的题有hdu 5050。

SuperGCD 洛谷 P2152题目描述:求2个正整数a,b的最大公约数,0 < a, b ≤ 10的10000次方 。

不过,由于OJ都支持java,比赛的时候直接用java函数处理大数是最简单的:

import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger a = in.nextBigInteger();
        BigInteger b = in.nextBigInteger();
        System.out.println(a.gcd(b));
    }
}

04、LCM

a和b的最小公倍数lcm(a, b),可以从算术基本定理推理得到。
算术基本定理(唯一分解定理):任何大于1的正整数n都可以唯一分解为有限个素数的乘积:image.png
,其中

image.png

都是正整数,image.png

都是素数且从小到大。
设:image.png

那么:

image.png


推出:

image.png


注意先做除法再做乘法,如果先做乘法可能会溢出。

int lcm(int a, int b){ 
    return a / gcd(a, b) * b;
}

05、例题

(1)hdu 5019
题目描述:给出整数x、y、k,求x、y的第k大公约数。
题解:先求最大公因数d = gcd(x, y),由于其他公因子都是d的因子,那么从1到sqrt(d)(注意不需要到d)逐个检查是否能整除d,即可找到所有公因子。

(2)hdu 2503
题目描述:给出2个分数a/b和c/d,求a/b + c/d,要求是最简形式。
题解:a/b + c/d = (ad + bc) / bd,分子和分母除以两者的最大公约数。

(3)hdu 2504
题目描述:已知a和b,求满足gcd(a,c) = b的最小的c。
题解:暴力搜b到a*b内符合条件的c。

(4)hdu 4497
题目描述:给定两个正整数G、L,问满足gcd(x, y, z) = G和lcm(x, y, z) = L的(x, y, z)有多少个?注意,(1, 2, 3)和(1, 3, 2)是不同的。
题解。此题利用了GCD的几个性质:
1)若gcd(a, b) = d,则gcd(a/d, b/d) = 1,即a/d与b/d互素;

image.png


若L % G ≠ 0,显然无解。下面分析L % G = 0的情况。
把问题转化为:满足gcd(x/G, y/G, z/G) = 1和lcm(x/G,y/G,z/G)= L/G的(x/G, y/G, z/G)有多少个。下面用排列组合分析有多少种情况。
根据算术基本定理,把x/G、y/G、z/G写成:

image.png


式子要满足x/G、y/G、z/G互素的条件。以1,j,ki}为例,其中至少有1个应该等于0。
另外,把L/G写成:L/G=地s式子要满足lcm(x/G,y/G,z/G) =L/G。以i1,j,k1}为例,允许的情况是:
1){0,0,t1,有三种排列;
2) {0,ti,t1),有三种排列;
3){0,ti,1~ti-1},有(ti-1)*6种排列;
加起来一共有 t;*6种排列。
最后问题转化为求t1t2、t3,即分解 L/G 的质因子

目录
相关文章
|
1月前
|
算法 安全 数据挖掘
解锁编程之门:数论在算法与加密中的实用应用
解锁编程之门:数论在算法与加密中的实用应用
数论整理之欧几里得算法gcd
数论整理之欧几里得算法gcd
|
算法 程序员
算法集训 | 暑期刷题营】8.12题---数论
算法集训 | 暑期刷题营】8.12题---数论
算法集训 | 暑期刷题营】8.12题---数论
|
算法 C++
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
75 0
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
|
算法 C++
算法基础系列第四章——数论之从欧拉卷到欧几里得(1)
算法基础系列第四章——数论之从欧拉卷到欧几里得(1)
132 0
算法基础系列第四章——数论之从欧拉卷到欧几里得(1)
|
算法 C++
算法基础系列第四章——数论之质数与约数(2)
算法基础系列第四章——数论之质数与约数(2)
102 0
算法基础系列第四章——数论之质数与约数(2)
|
机器学习/深度学习 算法 C++
算法基础系列第四章——数论之质数与约数(1)
算法基础系列第四章——数论之质数与约数(1)
143 0
算法基础系列第四章——数论之质数与约数(1)
|
算法
【算法合集】关于数论
裴蜀定理:若 a, b是整数,且 (a, b) = d,那么对于任意的整数 x, y, ax + by 都一定是 d的倍数,特别地,一定存在整数 x, y使 ax + by = d成立。
90 0
【算法合集】关于数论
|
人工智能 算法
算法模版:数论之约数全家桶
算法模版:数论之约数全家桶
算法模版:数论之约数全家桶