algorithm - 找到以 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) .

从if product(a[i...j])%K==0的原理来看, 然后 product(a[i...j+k])%K==0 ，你可以，对于每个 i , 执行二进制搜索以找到第一个 j其中 product(a[i..j])%K==0 .

在第一遍中，找出最小长度是多少。然后做另一遍查找和打印 which i有那个长度。

那是 O(n log^2 n) .对于 2*10^5 这应该足够了。特地给出答案可以有O(n^2)项目(例如 n/2 个子数组，每个子数组有 n/2 个项目)。