查找以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項）。