English · Original
Chinese · Translation
Formal · Original
Molly Hooper has _n_ different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The _i_\-th of them has affection value _a__i_.
Molly wants Sherlock to fall in love with her. She intends to do this by mixing a contiguous segment of chemicals together to make a love potion with total affection value as a non-negative **integer** power of _k_. Total affection value of a continuous segment of chemicals is the sum of affection values of each chemical in that segment.
Help her to do so in finding the total number of such segments.
## Input
The first line of input contains two integers, _n_ and _k_, the number of chemicals and the number, such that the total affection value is a non-negative power of this number _k_. (1 ≤ _n_ ≤ 105, 1 ≤ |_k_| ≤ 10).
Next line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — affection values of chemicals.
## Output
Output a single integer — the number of valid segments.
[samples]
## Note
Do keep in mind that _k_0 = 1.
In the first sample, Molly can get following different affection values:
* 2: segments \[1, 1\], \[2, 2\], \[3, 3\], \[4, 4\];
* 4: segments \[1, 2\], \[2, 3\], \[3, 4\];
* 6: segments \[1, 3\], \[2, 4\];
* 8: segments \[1, 4\].
Out of these, 2, 4 and 8 are powers of _k_ = 2. Therefore, the answer is 8.
In the second sample, Molly can choose segments \[1, 2\], \[3, 3\], \[3, 4\].
Molly Hooper 有 #cf_span[n] 种不同的化学试剂排成一行。每种化学试剂都有一个情感值，第 #cf_span[i] 种化学试剂的情感值为 #cf_span[ai]。
Molly 希望 Sherlock 爱上她。她打算通过混合一段连续的化学试剂来制作一种魔药，使得总情感值为 #cf_span[k] 的非负整数次幂。一段连续化学试剂的总情感值等于该段中所有化学试剂情感值的和。
请帮助她找出满足条件的连续段的总数。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]，分别表示化学试剂的数量以及总情感值必须是其非负整数次幂的数 #cf_span[k]。（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ |k| ≤ 10]）。
接下来一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）—— 化学试剂的情感值。
请输出一个整数——满足条件的连续段的数量。
请注意，#cf_span[k0 = 1]。
在第一个样例中，Molly 可以得到以下不同的总情感值：
其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。
在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]，分别表示化学试剂的数量以及总情感值必须是其非负整数次幂的数 #cf_span[k]。（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ |k| ≤ 10]）。接下来一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）—— 化学试剂的情感值。
## Output
请输出一个整数——满足条件的连续段的数量。
[samples]
## Note
请注意，#cf_span[k0 = 1]。
在第一个样例中，Molly 可以得到以下不同的总情感值：
#cf_span[2]：段 #cf_span[[1, 1]]、#cf_span[[2, 2]]、#cf_span[[3, 3]]、#cf_span[[4, 4]]；
#cf_span[4]：段 #cf_span[[1, 2]]、#cf_span[[2, 3]]、#cf_span[[3, 4]]；
#cf_span[6]：段 #cf_span[[1, 3]]、#cf_span[[2, 4]]；
#cf_span[8]：段 #cf_span[[1, 4]]。
其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。
在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of chemicals.
Let $ k \in \mathbb{Z} \setminus \{0\} $, $ |k| \leq 10 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in [-10^9, 10^9] $.
Let $ S(i,j) = \sum_{\ell=i}^{j} a_\ell $ denote the sum of the contiguous segment from index $ i $ to $ j $, for $ 1 \leq i \leq j \leq n $.
Let $ P = \{ k^m \mid m \in \mathbb{Z}_{\geq 0} \} $ be the set of non-negative integer powers of $ k $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq |k| \leq 10 $
3. $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of pairs $ (i,j) $ with $ 1 \leq i \leq j \leq n $ such that $ S(i,j) \in P $.
API Response (JSON)
{
"problem": {
"name": "C. Molly's Chemicals",
"description": {
"content": "Molly Hooper has _n_ different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The _i_\\-th of them has affection value _a__i_. Molly wants Sherlock to fall in lov",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF776C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Molly Hooper has _n_ different kinds of chemicals arranged in a line. Each of the chemicals has an affection value, The _i_\\-th of them has affection value _a__i_.\n\nMolly wants Sherlock to fall in lov...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Molly Hooper 有 #cf_span[n] 种不同的化学试剂排成一行。每种化学试剂都有一个情感值，第 #cf_span[i] 种化学试剂的情感值为 #cf_span[ai]。\n\nMolly 希望 Sherlock 爱上她。她打算通过混合一段连续的化学试剂来制作一种魔药，使得总情感值为 #cf_span[k] 的非负整数次幂。一段连续化学试剂的总情感值等于该段中所有化学试剂情感值的和。\n\n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of chemicals. \nLet $ k \\in \\mathbb{Z} \\setminus \\{0\\} $, $ |k| \\leq 10 $. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, wh...",
"is_translate": false,
"language": "Formal"
}
]
}