查找以K为因子的最小长度间隔

Question

给定整数K和一个N个整数列表。我们需要在列表中找到所有可能的最短间隔，使得每个间隔中整数的乘积是K的倍数。

示例：设N = 6，K = 5，数组为[2,9 ，4,3,16]，则此处的最小间隔长度为2，其乘积为K.的倍数。

区间：[1,2]，[2,3]，[3,4]，[4,5 ]。

现在我需要找到最小长度和所有间隔开始和结束。

但问题是约束很大，1≤N≤2×10 ^5,1≤K≤10^ 17，数组元素达到10^15。

Answer 1

您可以使用分段树来计算product(a[i...j])%K中的O(log N)。

从原理上说，如果product(a[i...j])%K==0，然后product(a[i...j+k])%K==0，你可以为每个i，执行二进制搜索找到第一个j其中product(a[i..j])%K==0。

在第一遍中，查找最小长度是多少。然后再通过发现并打印哪个i的长度。

这就是O(n log^2 n)。对于2 * 10^5应该足够了。特别给出的答案可以有O(n^2)项目（例如n/2个子阵列，每个项目n/2项）。