蓝桥杯数论总结：最大公约数和最小公倍数

树欲静而风不止慢一点吧

已于 2023-05-27 15:19:03 修改

阅读量1.1k

点赞数 5

分类专栏：一个电气学子的编程觉悟史蓝桥杯国赛混国三数据结构与算法总结文章标签：蓝桥杯数论 python 最大公约数算法

于 2023-05-22 19:07:10 首次发布

本文链接：https://blog.csdn.net/HP_C2H2/article/details/130809689

版权

一个电气学子的编程觉悟史同时被 3 个专栏收录

18 篇文章

订阅专栏

蓝桥杯国赛混国三

8 篇文章

订阅专栏

数据结构与算法总结

5 篇文章

订阅专栏

本文介绍了Python中最大公约数gcd和最小公倍数lcm的使用，包括辗转相除法的手写实现，lcm的推导及性质证明。同时提供了若干编程题目的描述和解决方案，涉及蓝桥杯和洛谷平台的相关题目，如核桃的数量、等差数列和Hankson的趣味题等。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

本文先是给出Python中gcd的使用实例和手写方法，以及lcm的手写方法，而后给出lcm表达式的推导和gcd性质的证明。再而给出了一份gcd的题单，以及部分题目的题面和题解。

最大公约数

gcd是最大公约数的意思。Python的math库里有gcd函数。

在Python命令行运行gcd，可发现其可传入0、不会返回负数、可对多个数进行判断的性质。

from math import *
gcd(0,44)
44
gcd(0,0)
0
gcd(-6,-15)
3
gcd(-17,289)
17
gcd(17,-289)
17
gcd(48,96,120,688)
8

手写GCD

辗转相除法

容易证明， $gcd(a,b)=gcd(b,a \; mod \; b)$

于是可写如下代码：

def gcd(a,b):
    if b==0:return a
    else: return gcd(b,a%b)

由于在Python中，a%b当b为负数的时候结果为负数，所以此手写算法有可能返回负数。

最小公倍数

lcm是最小公倍数的意思。在Python里有lcm函数，但是蓝桥杯用的环境是Python3.8.6的，所以只能借助gcd函数写lcm函数了。代码如下：

from math import *
def lcm(a,b):
    return a//gcd(a,b)*b

借用表达式 $lcm(a,b)=a*b/gcd(a,b)$ 。

推导LCM函数表达式

由算数基本定理：任何一个大于1的正整数n，都可以唯一分解成有限个素数的乘积。

则有 $n=p_{1}^{c_{1}}*p_{2}^{c_{2}}*...*p_{m}^{c_{m}}$

$c_{i}$ 是非负整数， $p_{i}$ 是互不相同的素数，且随 $i$ 增大， $p_{i}$ 数值不减。

设 $a=p_{1}^{c_{1}}*p_{2}^{c_{2}}*...*p_{m}^{c_{m}}$ ， $b=p_{1}^{f_{1}}*p_{2}^{f_{2}}*...*p_{m}^{f_{m}}$

则有

$gcd(a,b)=p_{1}^{\min(c_{1},f_{1})}*=p_{2}^{\min(c_{2},f_{2})}*...*p_{m}^{\min(c_{m},f_{m})}$

$lcm(a,b)=p_{1}^{\max(c_{1},f_{1})}*=p_{2}^{\max(c_{2},f_{2})}*...*p_{m}^{\max(c_{m},f_{m})}$

所以

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

则有

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

GCD基本性质

(1) $gcd(a, b) = gcd(a, a+b) = gcd(a, k*a+b)$

(2) $gcd(k*a, k*b) = 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+c*b,b)= gcd(a, b)$

性质的证明

取模运算基本性质

请看此篇文章的前五条性质。

最大公约数 —— Greatest Common Divisor(GCD) - 知乎 (zhihu.com)

证明

（1）

（2）

（3）使用算数基本定理证明，不再赘述。

（4）

（5）和第一条等价。

GCD/LCM题单

蓝桥oj

210：核桃的数量
192：等差数列
520： Hankson 的趣味题
120：最大比例
2131：寻找整数
2133 GCD

洛谷

P8792 [蓝桥杯 2022 国 A] 最大公约数
https://www.luogu.com.cn/problem/P8792

题干和题解

核桃的数量

题目描述

小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

各组的核桃数量必须相同
各组内必须能平分核桃（当然是不能打碎的）
尽量提供满足 1,2 条件的最小数量（节约闹革命嘛）

输入描述

输入一行 a,b,c，都是正整数，表示每个组正在加班的人数，用空格分开(a,b,c<30)。

输出描述

输出一个正整数，表示每袋核桃的数量。

输入输出样例

示例

输入

2 4 5

输出

求解

不废话，直接上代码。

from math import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
a,b,c=map(int,input().split())
t1=max(lcm(a,b),lcm(b,c))
t2=max(t1,lcm(a,c))
print(int(t2))

等差数列

题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入描述

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)

其中，2≤N≤10^5，0≤Ai≤10^9。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 6 4 10 20

输出

样例说明：包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

求解

放图解释。

an=a1+（n-1）*d

可知，对于每个ai，ai-a1=（n-1）d。取传入数据最小的为a1。

对i>=2的ai，后一个减前一个的操作，得到它们之间的距离。

对这些距离进行gcd，如果为0，则直接输出数组长度。如果不为0，则对每个距离除以d，求和后+1（算上不参与计算的a1）得到答案。

from math import gcd
n=int(input())
s=list(map(int,input().split()))
s.sort()
a1=s[0]
ns=[i-a1 for i in s]
ns[0]=ns[1]
for i in range(1,n-1):
    ns[i]=ns[i+1]-ns[i]

d=gcd(0,ns[0])
for i in range(1,n-1):
    d=gcd(d,ns[i])

if d==0:
    print(n)
else:
    ans=1
    for i in range(n-1):
        ans+=ns[i]//d
    print(ans)

Hankson的趣味题

题目描述

Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：

x 和 a0 的最大公约数是 a1；
x 和 b0 的最小公倍数是 b1。

Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。

输入描述

第一行为一个正整数 n，表示有 n 组输入数据。

接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。

其中，保证有 1≤a0，a1，b0，b1≤2×10^9且n≤2000。

输出描述

输出共 n 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 x，请输出 0；若存在这样的 x，请输出满足条件的 x 的个数。

输入输出样例

示例 1

输入

2
41 1 96 288
95 1 37 1776

输出

6
2

求解

已知x是b1的因数，那么存在一个y，使得x*y=b1。这样在对x的遍历中，x可以取根号，高效降低时间复杂度。注意，x的遍历范围是1到int(sqrt(b1))，而不是a1到int(sqrt(b1))，这是因为x没有a1作为因子时，y可能有a1这个因子。

from math import *
def lcm(a,b):
    return a*b//gcd(a,b)
n=int(input())
for _ in range(n):
    ans=0
    a0,a1,b0,b1=map(int,input().split())
    for x in range(1,int(sqrt(b1))+1):
        if b1%x==0:
            if gcd(a0,x)==a1 and lcm(x,b0)==b1:
                ans+=1
            y=b1//x
            if x==y:continue
            if gcd(a0,y)==a1 and lcm(y,b0)==b1:
                ans+=1
    print(ans)