区间最大公约数

Question

4

给定一个大小为 N 的数组。有 Q 个查询，需要计算 L 和 R 之间的 gcd，其中 L 和 R 满足 1 ≤ L ≤ R ≤ N。

如何高效地计算它，因为暴力方法会失败。

- user4447943

1

如果我理解正确，数组的目的是帮助您有效地计算GCD。您的数组中的数据类型是什么？您可以选择它吗？ - fjardon

3

最大公约数是满足结合律的，因此您可以使用通常的基于树的方法（一个节点存储其覆盖范围内所有项的最大公约数，可以通过仅考虑其直接子节点的最大公约数来构建）。然后查询仅需要 O(log n) 个最大公约数。 - harold

你的描述有点不清楚。如果我理解正确，对于每个Q查询，您都会得到一个L和R，并且需要计算gcd（L，R）。是这样吗？@harold：似乎不太可能OP需要计算范围内所有整数的同时gcd：对于非平凡范围，该gcd始终为1，因为gcd（n，n + 1）= 1。 - Mark Dickinson

@harold。嗯，也许吧。从问题的措辞中我真的无法确定OP想要什么。 "L和R之间的gcd"是什么意思？ - Mark Dickinson

2

猜测这可能来自于http://www.codechef.com/problems/GCDQ。 - Mark Dickinson

显示剩余5条评论

3个回答

3

使用线段树可以在适度的时间内进行预处理和查询。使用线段树，预处理时间为O(n)，GCD查询时间为O(Logn)。所需额外空间为O(n)以存储线段树。

线段树的表示：

- 叶节点是输入数组的元素。 - 每个内部节点表示其下所有叶子的GCD。

树的数组表示用于表示线段树，即对于索引i处的每个节点，

- 左孩子位于索引2 * i + 1处。 - 右孩子位于2 * i + 2处，父节点位于floor((i-1)/2)。

- GorvGoyl

0

或者使用O(n log n)处理和每个查询O(1)的稀疏表

- George Ogden

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kribesk · Accepted Answer

GCD是可加和可交换的。这意味着线段树可以在每个区间GCD查询中使用log(N)的时间解决此问题。