我有x个整数数组，我需要回答y个查询。每个查询有3个整数(Number, Left index, Right index)。我需要计算GCD(数字，数组[I])。I在查询中指定的左-右范围内。现在我需要输出在GCD计算中可以获得的最大数量。
示例->假设数字为4 5 8查询->(6,1,3)——(Number,Left Index,Right Index) GCD(6,4) = 2 GCD(6,5) = 1 GCD(6,8) = 2
所以答案是2。如果我在数组中有10^5个元素，我需要回答10^5个查询?
我想做一些预处理，但没有得到任何想法。
可以存储数组元素分解的每个素数的索引，对于查询数字，查看它在给定范围内的分解索引，并找到它们之间的最大GCD。
索引可以实现为对列表(在数组中的位置，素数幂)，其中搜索段是在log中。
。如果数组是[4,5,8,12,3]，那么我们有3个不同的质数(2,3,5)和索引:
2 -> [(0, 4), (2, 8), (3, 4)]
3 -> [(3, 3), (4, 3)]
5 -> [(1,5)]
对于查询(6,1,3)，由于6=2*3必须查找子索引:
2 -> [(2, 8), (3, 4)]
3 -> [(3, 3)]
对这些子索引进行并行处理，并对质数的GCD进行乘积(查询数中质数幂的最小值与索引第二元素)，将得到所有可能的GCD