@@ -72,3 +72,124 @@ def GCD(a: int, b: int) -> int:
7272```
7373
7474上面的代码会报栈溢出。原因在于如果 a 和 b 相差比较大的话，递归次数会明显增加，要比辗转相除法递归深度增加很多，最坏时间复杂度为 O(max(a, b)))。这个时候我们可以将` 辗转相除法 ` 和` 更相减损术 ` 做一个结合，从而在各种情况都可以获得较好的性能。
75+
76+ ## 实例解析
77+
78+ ### 题目描述
79+
80+ ```
81+ 给你三个数字 a，b，c，你需要找到第 n 个（n 从 0 开始）有序序列的值，这个有序序列是由 a，b，c 的整数倍构成的。
82+
83+ 比如：
84+ n = 8
85+ a = 2
86+ b = 5
87+ c = 7
88+
89+ 由于 2，5，7 构成的整数倍构成的有序序列为 [1, 2, 4, 5, 6, 7, 8, 10, 12, ...]，因此我们需要返回 12。
90+
91+ 注意：我们约定，有序序列的第一个永远是 1。
92+ ```
93+
94+ ### 思路
95+
96+ 大家可以通过 [ 这个网站] ( https://binarysearch.com/problems/Divisible-Numbers " binary search ") 在线验证。
97+
98+ 一个简单的思路是使用堆来做，唯一需要注意的是去重，我们可以使用一个哈希表来记录出现过的数字，以达到去重的目的。
99+
100+ 代码：
101+
102+ ``` py
103+ ss Solution:
104+ def solve (self n , a , b , c ):
105+ seen = set ()
106+ h = [(a, a, 1 ), (b, b, 1 ), (c, c, 1 )]
107+ heapq.heapify(h)
108+
109+ while True :
110+ cur, base, times = heapq.heappop(h)
111+ if cur not in seen:
112+ n -= 1
113+ seen.add(cur)
114+ if n == 0 :
115+ return cur
116+ heapq.heappush(h, (base * (times + 1 ), base, times + 1 ))
117+ ```
118+
119+ 对于此解法不理解的可先看下我之前写的 [ 几乎刷完了力扣所有的堆题，我发现了这些东西。。。（第二弹） ] ( https://lucifer.ren/blog/2021/01/19/heap-2/ " 几乎刷完了力扣所有的堆题，我发现了这些东西。。。（第二弹） ")
120+
121+ 然而这种做法时间复杂度太高，有没有更好的做法呢？
122+
123+ 实际上，我们可对搜索空间进行二分。首先思考一个问题，如果给定一个数字 x，那么有序序列中小于等于 x 的值有几个。
124+
125+ 答案是 x // a + x // b + x // c 吗？
126+
127+ > // 是地板除
128+
129+ 可惜不是的。比如 a = 2, b = 4, n = 4，答案显然不是 4 // 2 + 4 // 4 = 3，而是 2。这里出错的原因在于 4 被计算了两次，一次是 $2 * 2 = 4$，另一次是 $4 * 1 = 4$。
130+
131+ 为了解决这个问题，我们可以通过集合论的知识。
132+
133+ 一点点集合知识：
134+
135+ - 如果把有序序列中小于等于 x 的可以被 x 整除，且是 a 的倍数的值构成的集合为 SA，集合大小为 A
136+ - 如果把有序序列中小于等于 x 的可以被 x 整除，且是 b 的倍数的值构成的集合为 SB，集合大小为 B
137+ - 如果把有序序列中小于等于 x 的可以被 x 整除，且是 c 的倍数的值构成的集合为 SC，集合大小为 C
138+
139+ 那么最终的答案就是 SA ，SB，SC 构成的大的集合（需要去重）的中的数字的个数，也就是：
140+
141+ $$
142+ A + B + C - sizeof(SA \cap SB) - sizeof(SB \cap SC) - sizeof(SA \cap SC) + sizeof(SA \cap SB \cap SC)
143+ $$
144+
145+ 问题转化为 A 和 B 集合交集的个数如何求？
146+
147+ > A 和 B，B 和 C， A 和 C ，甚至是 A，B，C 的交集求法都是一样的。
148+
149+ 实际上， SA 和 SB 的交集个数就是 x // lcm(A, B)，其中 lcm 为 A 和 B 的最小公倍数。而最小公倍数则可以通过最大公约数计算出来：
150+
151+ ``` py
152+ def lcm (x , y ):
153+ return x * y // gcd(x, y)
154+
155+ ```
156+
157+ 接下来就是二分套路了，二分部分看不懂的建议看下我的[ 二分专题] ( https://github.com/azl397985856/leetcode/blob/master/91/binary-search.md " 二分专题 ") 。
158+
159+ ### 代码（Python3）
160+
161+ ``` py
162+ class Solution :
163+ def solve (self n , a , b , c ):
164+ def gcd (x , y ):
165+ if y == 0 :
166+ return x
167+ return gcd(y, x % y)
168+
169+ def lcm (x , y ):
170+ return x * y // gcd(x, y)
171+
172+ def possible (mid ):
173+ return (mid // a + mid // b + mid // c - mid // lcm(a, b) - mid // lcm(b, c) - mid // lcm(a, c) + mid // lcm(a, lcm(b, c))) >= n
174+
175+ l, r = 1 , n * max (a, b, c)
176+ while l <= r:
177+ mid = (l + r) // 2
178+ if possible(mid):
179+ r = mid - 1
180+ else :
181+ l = mid + 1
182+ return l
183+
184+ ```
185+
186+ ** 复杂度分析**
187+
188+ - 时间复杂度：$logn$。
189+ - 空间复杂度：gcd 和 lcm 的递归树深度，基本可忽略不计。
190+
191+ ## 总结
192+
193+ 通过这篇文章，我们不仅明白了最大公约数的** 概念以及求法** 。也形象化地感知到了最大公约数计算的** 原理** 。最大公约数和最小公倍数是两个相似的概念， 关于最大公约数和最小公倍数的题目在力扣中不算少，大家可以通过** 数学标签** 找到这些题。更多关于算法中的数学知识，可以参考这篇文章[ 刷算法题必备的数学考点汇总 ] ( https://mp.weixin.qq.com/s?__biz=MzI4MzUxNjI3OA==&mid=2247485590&idx=1&sn=e3f13aa02fed4d4132146e193eb17cdb&chksm=eb88c48fdcff4d99b44d537459396589b8987f89a8c21085a945ca8d5e2b0b140c13aef81d91&token=1223087516&lang=zh_CN#rd " 刷算法题必备的数学考点汇总 ")
194+
195+ > 这篇文章的第二篇也马上要发布了。
0 commit comments