算法题中常用数学概念、公式、方法汇总(其三:数论)

2023-12-25 20:43:11

数论

最大公约数

对于正整数 A A A B B B而言,若正整数 X X X是同时能够被 A A A和$ 整除的最大正整数,则称 整除的最大正整数,则称 整除的最大正整数,则称X 是 是 A 和 和 B$的最大公约数 Greatest Common DivisorGCD

一般使用辗转相除法来求两个数的最大公约数,其流程如下

  1. 规定两个数中的较大值和较小值分别为 A A A B B B,然后进行循环
  2. 计算 X = A % B X=A\%B X=A%B,其中 % \% %为求余符号
  3. 若此时 X = 0 X=0 X=0,则此时 B B B是两数之间的最大公约数,退出循环
  4. 若此时 X ≠ 0 X\neq0 X=0,则需要将 B B B是两数赋值给 A A A,余数 X X X赋值给 B B B重复第二步

上述过程用代码表示为

def get_gcd(A, B):
    A, B = max(A,B), min(A,B)
    while A % B != 0:
        X = A % B
        A = B
        B = X
    return B

A, B = 144, 60
print(get_gcd(A, B))    # 输出12

在python中,math库中自带的gcd()函数,也可以直接计算两个数的最大公约数,其代码为

from math import gcd

A, B = 144, 60
print(gcd(A, B))        # 输出12

最小公倍数

对于正整数 A A A B B B而言,若正整数 Y Y Y是同时能够整除 A A A B B B的最小正整数,则称 Y Y Y A A A B B B最小公倍数(Lowest Common Multiple,LCM)

已知一个正整数 A A A B B B的最大公约数为 X X X,最小公倍数为 Y Y Y,那么以下关系成立

X ? Y = A ? B X*Y=A*B X?Y=A?B

故求出正整数 A A A B B B的最大公约数为 X X X,就可以求出最小公倍数 Y Y Y

Y = A ? B X Y=\frac{A*B}{X} Y=XA?B?

用代码表示为

from math import gcd

A, B = 144, 60
print(A * B // gcd(A, B))    # 输出720

*裴蜀定理

裴蜀定理,也称为贝祖定理(Bézout’s identity),指的是对于任意两个非零整数 ab,存在整数 xy,使得 ax + by = gcd(a, b)

这个定理表明,对于任意两个整数,其最大公约数可以由它们的线性组合表示。其中,xy 是整数系数,可以是正数、负数或零。

举个例子。考虑两个整数 a = 42b = 30ab 的最大公约数为gcd(42, 30) = 6

那么我们可以找到(x, y) = (2, -3),使得42x + 30y = 6成立。

题目LeetCode1250. 检查「好数组」就用到了裴蜀定理。我也贡献了一篇精华题解,感兴趣的同学可以看看这题。

质数

如果一个大于 1 1 1的正整数 X X X的因数只有 1 1 1和他自身,那么称 X X X质数或素数(prime),否则称为合数(composite)

特别规定:最小的质数是 2 2 2。正整数 0 0 0 1 1 1既不是质数也不是合数。

单个质数的判断

要判断一个正整数 X X X是否为质数,最简单的方式就是枚举2X-1的每一个数,检查这些数是否可以被 X X X整除。如果出现了任何一个数可以被 X X X整除,那么 X X X是一个合数;反之 X X X是一个质数。这种方法叫做试除法

其代码实现如下

# 初始化一个标志,表示默认x是一个质数
isPrime = True
# 枚举从2到x-1的每一个数
for i in range(2, x):
    # 如果x可以整除i,说明x是合数
    if x % i == 0:
        isPrime = False
        break

# 退出循环后,根据isPrime的结果,可判断x是否是一个质数

上述过程的时间复杂度为O(x)

实际上,由于一个正整数的因数总是成对出现的,无需枚举2X-1的每一个数,只需要枚举枚举2sqrt(X)就可以了。其证明如下:

假设 X X X 是一个正整数且是合数,即 X X X 可以被分解为两个正整数 a a a b b b,其中 1 < a ≤ b < X 1<a≤b<X 1<ab<X。那么至少其中一个数一定小于等于 X \sqrt{X} X ? ,另一个数一定大于等于 X \sqrt{X} X ?,即 1 < a ≤ X ≤ b < X 1<a≤\sqrt{X}≤b<X 1<aX ?b<X。因此只需要枚举到 X \sqrt{X} X ?,找到正整数 a a a 即可。

其代码实现如下

from math import sqrt, floor

# 初始化一个标志,表示默认x是一个质数
isPrime = True
# 枚举从2到floor(sqrt(x))的每一个数
# 注意此处使用了向下取整
for i in range(2, floor(sqrt(x))+1):
    # 如果x可以整除i,说明x是合数
    if x % i == 0:
        isPrime = False
        break

# 退出循环后,根据isPrime的结果,可判断x是否是一个质数

上述过程的时间复杂度为O(sqrt(x))

质数筛

上一小节主要讲解了单个正整数X的质数判断。如果将问题转变为小于等于N的所有正整数的质数判断,则需要用到质数筛。所谓质数筛,指的是类似筛子一样,可以高效地把合数过滤掉,留下质数。

质数筛分为埃氏筛(Sieve of Eratosthenes)欧拉筛(Sieve of Euler),其本质大同小异。

埃氏筛

埃氏筛基于以下原理:假设 X X X 是一个质数,那么 X X X 的正整数倍 2 X 2X 2X 3 X 3X 3X,…, m X mX mX是一个合数。

因此我们需要构建一个长度为n+1的数组sieve,初始化sieve[x]均为True,表示默认正整数x为质数。

枚举从2floor(sqrt(x))的每一个正整数数x。若

  • x是质数,即sieve[x] == True。则再次进行内层循环,将xm倍(m >= 2)均筛选出来,在数组sieve中标记为合数。
  • x是合数,即sieve[x] == False,则直接跳过。

其代码实现如下

from math import sqrt, floor

def sieve_of_eratosthenes(n):
    # 构建埃氏筛,长度为n+1,初始化均为True,表示默认为质数
    sieve = [True] * (n + 1)
    # 0和1不是质数
    sieve[0], sieve[1] = False, False  
    # 枚举从2到floor(sqrt(x))的每一个数x
    for x in range(2, floor(sqrt(n))+1):
        # 如果x是一个质数,则说明其m倍(m >= 2)的所有正整数是合数
        if sieve[x] == True:
            # 将mx标记为False
            for i in range(2*x, n + 1, x):
                sieve[i] = False
                
    # 退出循环后,sieve中所有为True的元素下标为质数
    primes = [i for i in range(n + 1) if sieve[i]]
    return primes

筛选过程中,每个合数会被其最小质因数标记,对于小于等于 n 的合数,其最小质因数不会超过sqrt(n)。因此,对于每个质数 p,它标记的合数个数约为 n/p

所以总的时间复杂度可以表示为: O ( n / 2 + n / 3 + n / 5 + . . . + n / p ) O(n/2 + n/3 + n/5 + ... + n/p) O(n/2+n/3+n/5+...+n/p),其中 p 是不超过 n 的最大质数,这个求和可以近似为 O ( n l o g ( l o g n ) ) O(nlog(logn)) O(nlog(logn))

*欧拉筛

大部分时候,埃氏筛的时间复杂度已经足够接近线性时间复杂度 O ( n ) O(n) O(n)。但埃氏筛仍然存在优化空间。

比如合数6 = 2 * 3,既是质数2的正整数倍,也是质数3的正整数倍。在埃氏筛中,合数6会在考虑质数2和质数3的时候被重复筛选,这造成了额外开销。

为了避免同一个合数被重复筛选,对于每一个合数,我们希望只它被其最小的质因数筛选。

欧拉筛就是埃氏筛的改良算法,其具体过程如下:

构建一个长度为n+1的数组sieve,初始化sieve[x]均为True,表示默认正整数x为质数。另外构建一个primes数组,用于储存枚举过程中找到的质数。

枚举从2n的每一个正整数数x,然后执行以下操作

  • x是质数,即sieve[x] == True,则将x加入primes中。
  • 无论x是质数还是合数,都再次枚举质数数组primes中的每一个质数p。考虑正整数x*p。若
    • 如果正整数x*p超过最大范围n,则可以直接枚举质数数组primes的循环。
    • p必然是合数x*p的最小质因数,将sieve[x*p]标记为False
    • 如果x是合数且是p的倍数,这表示x的最小质因数是px*p 的最小质因数也必然是p。如果xp整除,并且继续用x的倍数标记后续的数,这些数会在后续的质数遍历中被重复标记,因为在之前的遍历中,x已经被p标记过了,所以在此处标记是多余的。因此,在发现xp整除时,就可以中断对p的遍历,避免重复标记。

举个例子,当x = 4时,此时primes = [2, 3]。考虑p = 2,把x * p = 8标记为合数后,由于x % p == 0,可以直接退出循环,不用再考虑p = 3的情况,去标记x * p = 12。因为12会在后续的x = 6的时候,在考虑p = 2时被标记为合数。如果此时对4 * 3 = 12进行标记,会导致后续的6 * 2 = 12出现重复标记。

其代码实现如下

def sieve_of_euler(n):
    # 构建欧拉筛,长度为n+1,初始化均为True,表示默认为质数
    sieve = [True] * (n + 1)
    # 0和1不是质数
    sieve[0], sieve[1] = False, False
    # 构建质数数组,初始化为空
    primes = []
    # 枚举所有从2到n的正整数x
    for x in range(2, n + 1):
        # 如果x是质数,则加入primes数组中
        if sieve[x]:
            primes.append(x)
        # 无论x是不是质数,都枚举x的p倍,即正整数xp,其中p是已经筛选出的质数
        for p in primes:
            # 如果xp超过了n,则可以直接退出当前循环
            if x * p > n:
                break
            # p必然是合数xp的最小质因数
            # 将xp标记为合数
            sieve[x * p] = False
            # 如果x是合数且是p的倍数,则可以直接退出当前循环
            if x % p == 0:
                break
    return primes

由于每一个数,最多只会被标记一次。所以欧拉筛的时间复杂度为 O ( n ) O(n) O(n)。由于是线性的时间复杂度,欧拉筛也被称为线性筛

多数情况下,更易于理解的埃氏筛已经足够优秀了,大家可以只掌握埃氏筛的方法。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/135207159
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。