English · Original
Chinese · Translation
Formal · Original
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 , 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
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 _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 108) — the elements of the array.
## Output
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_.
[samples]
## Note
In the first example the only subsegment is \[1\]. The sum equals 1, the product equals 1, so it suits us because .
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 . Subsegment \[3, 8, 1\] has sum 12 and product 24, so it suits us because .
Nastya 在她的生日那天收到了一个新数组，可以使用这个数组玩一个传统的 Byteland 游戏。然而，要玩这个游戏，玩家首先需要选择一个子段，使得该子段的乘积与和的比值等于给定常数 $k$，即 $\frac{\text{product}}{\text{sum}} = k$，其中 $\text{product}$ 是子段中所有整数的乘积，$\text{sum}$ 是它们的和。
Nastya 想知道有多少个子段满足上述条件。数组的子段是指数组中若干连续的整数。
第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 2·10^5$，$1 ≤ k ≤ 10^5$），其中 $n$ 是数组的长度，$k$ 是上述常数。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^8$）—— 数组的元素。
在唯一的一行中，输出满足乘积与和的比值等于 $k$ 的子段数量。
在第一个示例中，唯一的子段是 $[1]$。和等于 $1$，乘积等于 $1$，因此满足条件，因为 $\frac{1}{1} = 1 = k$。
在第二个示例中有两个符合条件的子段 — $[6, 3]$ 和 $[3, 8, 1]$。子段 $[6, 3]$ 的和为 $9$，乘积为 $18$，因此满足条件，因为 $\frac{18}{9} = 2 = k$。子段 $[3, 8, 1]$ 的和为 $12$，乘积为 $24$，因此满足条件，因为 $\frac{24}{12} = 2 = k$。
## Input
第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 2·10^5$，$1 ≤ k ≤ 10^5$），其中 $n$ 是数组的长度，$k$ 是上述常数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^8$）—— 数组的元素。
## Output
在唯一的一行中，输出满足乘积与和的比值等于 $k$ 的子段数量。
[samples]
## Note
在第一个示例中，唯一的子段是 $[1]$。和等于 $1$，乘积等于 $1$，因此满足条件，因为 $\frac{1}{1} = 1 = k$。在第二个示例中有两个符合条件的子段 — $[6, 3]$ 和 $[3, 8, 1]$。子段 $[6, 3]$ 的和为 $9$，乘积为 $18$，因此满足条件，因为 $\frac{18}{9} = 2 = k$。子段 $[3, 8, 1]$ 的和为 $12$，乘积为 $24$，因此满足条件，因为 $\frac{24}{12} = 2 = k$。
Let $ a = [a_1, a_2, \dots, a_n] $ be an array of positive integers, and let $ k $ be a positive integer constant.
A subsegment $ a[i:j] = (a_i, a_{i+1}, \dots, a_j) $ for $ 1 \leq i \leq j \leq n $ satisfies the condition if:
$$
\frac{\prod_{\ell=i}^j a_\ell}{\sum_{\ell=i}^j a_\ell} = k
$$
That is,
$$
\prod_{\ell=i}^j a_\ell = k \cdot \sum_{\ell=i}^j a_\ell
$$
Let $ P(i,j) = \prod_{\ell=i}^j a_\ell $ and $ S(i,j) = \sum_{\ell=i}^j a_\ell $. The goal is to count the number of pairs $ (i,j) $ with $ 1 \leq i \leq j \leq n $ such that:
$$
P(i,j) = k \cdot S(i,j)
$$
**Input:**
- $ n, k \in \mathbb{Z}^+ $, $ 1 \leq n \leq 2 \cdot 10^5 $, $ 1 \leq k \leq 10^5 $
- $ a_i \in \mathbb{Z}^+ $, $ 1 \leq a_i \leq 10^8 $
**Output:**
The number of subsegments $ [i,j] $ satisfying $ P(i,j) = k \cdot S(i,j) $.
API Response (JSON)
{
"problem": {
"name": "D. Nastya and a Game",
"description": {
"content": "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 arr",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF992D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 arr...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Nastya 在她的生日那天收到了一个新数组，可以使用这个数组玩一个传统的 Byteland 游戏。然而，要玩这个游戏，玩家首先需要选择一个子段，使得该子段的乘积与和的比值等于给定常数 $k$，即 $\\frac{\\text{product}}{\\text{sum}} = k$，其中 $\\text{product}$ 是子段中所有整数的乘积，$\\text{sum}$ 是它们的和。\n\nNastya 想...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of positive integers, and let $ k $ be a positive integer constant.\n\nA subsegment $ a[i:j] = (a_i, a_{i+1}, \\dots, a_j) $ for $ 1 \\leq i \\leq j \\leq n $ ...",
"is_translate": false,
"language": "Formal"
}
]
}