https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/?orderBy=most_votes
题解 :
由于非空子序列的数量高达
$$
2^n-1
$$
,直接回溯枚举是会超时的。不妨换一个视角,考虑值域。
多个数的最大公约数等于 g,也反过来说明这些数都是 g 的倍数。例如 [8,12,6] 的最大公约数是 2,这些数都是 2 的倍数。
那么,能不能反过来,枚举 g 的倍数呢?
1,2,3,
2,4,6,⋯
3,6,9,⋯
看上去运行时间是个平方级别的,会超时。
⌊
1
U
⌋
先别急着否定,这里得来点数学。
设 U=max(nums),那么 1 的倍数需要枚举 $⌊U1⌋\left\lfloor\dfrac{U}{1}\right\rfloor⌊
1
U
⌋ $个,222 的倍数需要枚举 ⌊U2⌋\left\lfloor\dfrac{U}{2}\right\rfloor⌊2 U ⌋ 个,……,把这些加起来,去掉下取整,有4
$$⌊U1⌋+⌊U2⌋+⋯+⌊UU⌋≤U⋅(11+12+⋯+1U) \left\lfloor\dfrac{U}{1}\right\rfloor + \left\lfloor\dfrac{U}{2}\right\rfloor +\cdots + \left\lfloor\dfrac{U}{U}\right\rfloor \le U\cdot\left(\dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{U}\right)$$
右边括号中的叫做 调和级数部分和,可以看成是 $$O(logU)O(\log U)O(logU)$$ 的,因此枚举倍数的时间复杂度为 $$O(UlogU)O(U\log U)O(UlogU)$$,不会超时。
那么就枚举 $$i=1,2,⋯ ,Ui=1,2,\cdots,Ui=1,2,⋯,U$ 及其倍数,当作子序列中的数。
子序列中的数越多,g 就可能越小,就越可能等于 i。
例如,如果枚举 i=2 的倍数,其中 8 和 12 是在 $$nums\textit{nums}nums$$ 中的,但由于 8 和 12 的最大公约数等于 4,所以无法找到一个子序列,其最大公约数为 i。但如果还有 6 也在 $$nums\textit{nums}nums$$ 中,那么最大公约数等于 2,这样 i 就可以是一个子序列的最大公约数了。
代码实现时,需要用哈希表或者数组,记录每个数是否在 $$nums\textit{nums}nums$$ 中,从而加快判断。数组的效率会更高一些。