Nastya and a Game
Contest: Codeforces Round 489 (Div. 2)
Difficulty rating: 2100
Tags: brute force, implementation, math

Nastya received one more array on her birthday, this array can be used to play a traditional Byteland game on it. However, to play the game the players should first select such a subsegment of the array that $$\frac{p}{s} = k$$, where p is the product of all integers on the given array, s is their sum, and k is a given constant for all subsegments.

Nastya wonders how many subsegments of the array fit the described conditions. A subsegment of an array is several consecutive integers of the array.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 105), where n is the length of the array and k is the constant described above.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 108) — the elements of the array.

Output format:
In the only line print the number of subsegments such that the ratio between the product and the sum on them is equal to k.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the only subsegment is [1]. The sum equals 1, the product equals 1, so it suits us because $${ \frac { 1 } { 1 } } = 1$$.

There are two suitable subsegments in the second example — [6, 3] and [3, 8, 1]. Subsegment [6, 3] has sum 9 and product 18, so it suits us because $$\frac{18}{9}=2$$. Subsegment [3, 8, 1] has sum 12 and product 24, so it suits us because $$\frac{24}{12}=2$$.

Example input:
1 1
1

Example output:
1

Example input:
4 2
6 3 8 1

Example output:
2

Editorial:
Let's call numbers which are more than 1 as good. Notice the following fact:
If a subsegment is suitable, it contains not more than 60 good numbers.
Indeed, let's assume that a subsegment contains more than 60 good numbers. In this subsegment $$p \geq 2^{61} > 2 \cdot 10^{18}$$. At the same time, as $$k \leq 10^5$$, and $$s \leq n \cdot 10^{8} = 2 \cdot 10^{13}$$, there is $$s \cdot k \leq 2 \cdot 10^{18}$$. Therefore, this subsegment can't be suitable due to $$s \cdot k < p$$.
Let's keep all positions of good numbers in a sorted array. We sort out possible left border of a subsegment and then with binary search we find the next good number to the right of this left border. Then let's iterate from this found number to the right by the good numbers(that is we sort out the rightmost good number in a subsegment), until product of all numbers in the subsegment becomes more than $$2 \cdot 10^{18}$$ (it's flag which shows us, that product is too big for a suitable subsgment and we need to finish to iterate). We have shown above the number of iterations isn't more than 60. Now for sorted out the left border and the rightmost good number we only need to know the number of 1's which needs to be added to the right of the rightmost good number, as we can easily maintain sum and product in the subsegment during iterating. Then we need to check whether found number of 1's exists to the right of the rightmost good number. It can be checked if we look at the next good number's position.
Complexity is $${\mathcal {O}}(n\cdot \log(10^{18}))$$.
In order to check that $$a \cdot b$$ is more than $$2 \cdot 10^{18}$$, you shouldn't calculate $$\alpha$$ multiply by $$\beta$$, due to overflow. You must only check that $${ \frac { 2 \cdot 1 0 ^ { 1 8 } } { a } } \geq b$$.