title: Sliding window algorithm to calculate the list of all k-element contiguous subarray products of an array modulo p
body: <p>I have an array of <code>n</code> positive integers. I want to calculate a list of all contiguous subarray products of size <code>k</code> modulo <code>p</code>. For instance for the following array:</p>
  <p><code>a = [3, 12, 5, 2, 3, 7, 4, 3]</code></p>
  <p>with <code>k = 3</code> and <code>p = 12</code>, the ordered list of all <code>k</code>-sized contiguous subarray products will be:</p>
  <p><code>k_products = [180, 120, 30, 42, 84, 84]</code></p>
  <p>and modulo <code>p</code> we have:</p>
  <p><code>k_products_p = [0, 0, 6, 6, 0, 0]</code></p>
  <p>we can easily compute <code>k_products</code> using a sliding window. All we have to do is to compute the product for the first <code>k</code>-sized subarray and then compute the next elements of <code>k_product</code> using the following formula:</p>
  <p><code>k_product[i] = k_product[i - 1] * a[i + k] / a[i - 1]</code></p>
  <p>and after forming the whole list, we can compute <code>k_product[i] % p</code> for each <code>i</code> to get <code>k_product_p</code>. That's it. <code>O(n)</code> complexity is pretty good.</p>
  <p>But if the elements of <code>a[i]</code> are big, the elements of k_product may overflow, and thus we cannot compute <code>k_product_p</code>. Plus, we cannot, for example do the following:</p>
  <p><code>k_product[i] = ((k_product[i - 1] % p) * (a[i + k] % p) / (a[i - 1] % p)) % p  // incorrect</code></p>
  <p>So is there a fast algorithm to do this? Note that <code>p</code> is not necessarily prime and it is also not necessarily coprime to the elements of <code>a</code>.</p>
  <p>Edit: As mentioned in the comments, there will be no overflow in python, but working with very big numbers will be time-consuming.</p>