{"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 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.\n\nNastya wonders how many subsegments of the array fit the described conditions. A subsegment of an array is several consecutive integers of the array.\n\n## Input\n\nThe 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.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 108) — the elements of the array.\n\n## Output\n\nIn the only line print the number of subsegments such that the ratio between the product and the sum on them is equal to _k_.\n\n[samples]\n\n## Note\n\nIn the first example the only subsegment is \\[1\\]. The sum equals 1, the product equals 1, so it suits us because .\n\nThere 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 .","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Nastya 在她的生日那天收到了一个新数组，可以使用这个数组玩一个传统的 Byteland 游戏。然而，要玩这个游戏，玩家首先需要选择一个子段，使得该子段的乘积与和的比值等于给定常数 $k$，即 $\\frac{\\text{product}}{\\text{sum}} = k$，其中 $\\text{product}$ 是子段中所有整数的乘积，$\\text{sum}$ 是它们的和。\n\nNastya 想知道有多少个子段满足上述条件。数组的子段是指数组中若干连续的整数。\n\n第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 2·10^5$，$1 ≤ k ≤ 10^5$），其中 $n$ 是数组的长度，$k$ 是上述常数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^8$）—— 数组的元素。\n\n在唯一的一行中，输出满足乘积与和的比值等于 $k$ 的子段数量。\n\n在第一个示例中，唯一的子段是 $[1]$。和等于 $1$，乘积等于 $1$，因此满足条件，因为 $\\frac{1}{1} = 1 = k$。\n\n在第二个示例中有两个符合条件的子段 — $[6, 3]$ 和 $[3, 8, 1]$。子段 $[6, 3]$ 的和为 $9$，乘积为 $18$，因此满足条件，因为 $\\frac{18}{9} = 2 = k$。子段 $[3, 8, 1]$ 的和为 $12$，乘积为 $24$，因此满足条件，因为 $\\frac{24}{12} = 2 = k$。\n\n## Input\n\n第一行包含两个整数 $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$）—— 数组的元素。\n\n## Output\n\n在唯一的一行中，输出满足乘积与和的比值等于 $k$ 的子段数量。\n\n[samples]\n\n## Note\n\n在第一个示例中，唯一的子段是 $[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$。","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 $ satisfies the condition if:\n\n$$\n\\frac{\\prod_{\\ell=i}^j a_\\ell}{\\sum_{\\ell=i}^j a_\\ell} = k\n$$\n\nThat is,\n\n$$\n\\prod_{\\ell=i}^j a_\\ell = k \\cdot \\sum_{\\ell=i}^j a_\\ell\n$$\n\nLet $ 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:\n\n$$\nP(i,j) = k \\cdot S(i,j)\n$$\n\n**Input:**\n- $ n, k \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq k \\leq 10^5 $\n- $ a_i \\in \\mathbb{Z}^+ $, $ 1 \\leq a_i \\leq 10^8 $\n\n**Output:**\nThe number of subsegments $ [i,j] $ satisfying $ P(i,j) = k \\cdot S(i,j) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF992D","tags":["brute force","implementation","math"],"sample_group":[["1 1\n1","1"],["4 2\n6 3 8 1","2"]],"created_at":"2026-03-03 11:00:39"}}