最大公约数&最小公倍数

最大公约数 Greatest Common Divisor (GCD)整数 a 和 b 的 GCD 是指能同时整除 a 和 b 的最大整数记为 gcd(a,b)。由于 -a 的因子和 a 的因子相同因此 gcd(a, b)=gcd(lal, lb|)。编码时只关注正整数的最大公约数。

性质

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

2gcd(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 互素。这个定理很重要。

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

2、Python函数gcd()

gcd() 不会返回负数 (c++函数 std::__gcd() 可以返回负数)

gcd() 可以带多个参数 (在 3.9 版更改: 添加了对任意数量的参数的支持之前的版本只支持两个参数。)

from math import *
print(gcd(15,81))   #3
print(gcd(0,44))    #44
print(gcd(0,0))     #0
print(gcd(-6,-15))    #3
print(gcd(-17,289))    #17
print(gcd(17,-289))    #17
print(gcd(48,96,120,688))   #8,不过3.8版本还不支持多参数

3、手写gcd代码

手写gcd函数常用欧几里得算法。
辗转相除法求 gcd
gcd(a, b) = gcd(b, a mod b)
这是最常用的方法极为高效。
设 a>b辗转相除法的计算复杂度为 O((loga)^3)。以2为底
可能输出负数和库函数不同

辗转相除法两个正整数a和ba>b它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数。比如10和2525除以10商2余5那么10和25的最大公约数等同于10和5的最大公约数。

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

print(gcd(15,81))   #3
print(gcd(0,44))    #44
print(gcd(0,0))     #0
print(gcd(-6,-15))    #-3
print(gcd(-17,289))    #17
print(gcd(17,-289))    #-17
#print(gcd(48,96,120,688))   #8,不过3.8版本还不支持多参数

三、LCM最小公倍数

1、定义与性质

最小公倍数 LCMthe Least Common Multiple。

a 和 b 的最小公倍数 lcm(a,b)从算术基本定理推理得到。

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

n=(p1^c1)(p2^c2)...(pm^cm)其中 ci 都是正整数pi 都是素数且从小到大。

推导 LCM

设a=(p1^c1)(p2^c2)...(pm^cm)b=(p1^f1)(p2^f2)...(pm^fm)

那么gcd(a, b) = p1^min{c1, f1}*p2^min{c2, f2} *...* pm^min{cm, fm}

Icm(a, b) = p1^max{c1, f1}*p2^max{c2, f2} *...* pm^max{cm, fm}

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

即lcm(a, b)=a*b/gcd(a, b)=a/gcd(a, b)*b。

2、Python库函数lcm()

在 Python 新版本 ( Python3.9 才加入了 1 cm) 中有库函数 1cm()它可以带多个参数。

在 Python 的旧版本中并没有 lcm() 函数自己写一个 lcm()

>>> from math import *
>>> def lcm(x,y):
	    return x//gcd(x,y)*y
>>> lcm(2,3)
6

四、例题

1、核桃的数量2013年省赛lanqiaoOJ题号210

【题目描述】

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

1.各组的核桃数量必须相同

2.各组内必须能平分核桃 (当然是不能打碎的)

3.尽量提供满足 1,2 条件的最小数量 (节约闹革命嘛

【输入格式】

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

【输出格式】

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

这就是一道简单题啊

from math import *
def lcm(x,y):
    return x//gcd(x,y)*y
a,b,c=map(int,input().split())
k=lcm(a,b)
print(lcm(k,c))

2、等差数列2019年第十届省赛lanqiaoOJ题号192

【题目描述】

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列只记得其中 N 个整数。现在给出这 N 个整数小明想知道包含这 N 个整数的最短的等差数列有几项

【输入描述】

输入的第一行包含一个整数 N。第二行包含 N 个整数 A1, A2, ..., AN。注意 A1~AN 并不一定是按等差数列中的顺序给出对于所有评测用例2≤N≤1000000≤Ai≤10^9。

【输出描述】

输出一个整数表示答案

所有数字间距离最小的间隔是公差吗

并不是例如 {2, 5, 7}最小的间隔是 2但公差不是 2是 1。

这是 gcd 问题。把 n 个数据排序计算它们的间隔对所有间隔做 GCD结果为公差。

最少数量等于最大值-最小值) / 公差 + 1。

from math import *
n=int(input())
a=list(map(int,input().split()))
a.sort()
d=0
for i in range(1,n):
    d=gcd(d,a[i]-a[i-1])
if d==0:
    print(n)
else:
    print(a[-1]-a[0]//d+1)

3、Hankson 的趣味题lanqiaoOJ题号520

【题目描述】

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

1.x 和 a0 的最大公约数是 a1

2.x 和 b0 的最小公倍数是 b1。

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

【输入格式】

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

数据规模对于 100% 的数据保证有 1≤a0, a1, b0, b1≤2,000,000,000 且 n≤2000

【输出格式】

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

若不存在这样的 x 请输出0若存在这样的 x请输出满足条件的 x 的个数。

1暴力法

2优化

若 x 是 b1 的因子有 x*y=b1y 也可能是答案。·

只需要在范围 x<=sqrt(b1) 内查询同时判断 y 就行了。

但还是超时因为 gcd 计算也要花时间加上一个优化if b1%x==0表示 b1 是 x 的公倍数。

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