{"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 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.\n\nHelp her to do so in finding the total number of such segments.\n\n## Input\n\nThe 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).\n\nNext line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109) — affection values of chemicals.\n\n## Output\n\nOutput a single integer — the number of valid segments.\n\n[samples]\n\n## Note\n\nDo keep in mind that _k_0 = 1.\n\nIn the first sample, Molly can get following different affection values:\n\n*   2: segments \\[1, 1\\], \\[2, 2\\], \\[3, 3\\], \\[4, 4\\];\n    \n*   4: segments \\[1, 2\\], \\[2, 3\\], \\[3, 4\\];\n    \n*   6: segments \\[1, 3\\], \\[2, 4\\];\n    \n*   8: segments \\[1, 4\\].\n\nOut of these, 2, 4 and 8 are powers of _k_ = 2. Therefore, the answer is 8.\n\nIn the second sample, Molly can choose segments \\[1, 2\\], \\[3, 3\\], \\[3, 4\\].","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请帮助她找出满足条件的连续段的总数。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]，分别表示化学试剂的数量以及总情感值必须是其非负整数次幂的数 #cf_span[k]。（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ |k| ≤ 10]）。\n\n接下来一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ - 109 ≤ ai ≤ 109]）—— 化学试剂的情感值。\n\n请输出一个整数——满足条件的连续段的数量。\n\n请注意，#cf_span[k0 = 1]。\n\n在第一个样例中，Molly 可以得到以下不同的总情感值：\n\n \n\n \n\n \n\n其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。\n\n在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。\n\n## Input\n\n输入的第一行包含两个整数 #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]）—— 化学试剂的情感值。\n\n## Output\n\n请输出一个整数——满足条件的连续段的数量。\n\n[samples]\n\n## Note\n\n请注意，#cf_span[k0 = 1]。\n\n在第一个样例中，Molly 可以得到以下不同的总情感值：\n#cf_span[2]：段 #cf_span[[1, 1]]、#cf_span[[2, 2]]、#cf_span[[3, 3]]、#cf_span[[4, 4]]；\n#cf_span[4]：段 #cf_span[[1, 2]]、#cf_span[[2, 3]]、#cf_span[[3, 4]]；\n#cf_span[6]：段 #cf_span[[1, 3]]、#cf_span[[2, 4]]；\n#cf_span[8]：段 #cf_span[[1, 4]]。\n其中，#cf_span[2]、#cf_span[4] 和 #cf_span[8] 是 #cf_span[k = 2] 的幂，因此答案为 #cf_span[8]。\n\n在第二个样例中，Molly 可以选择段 #cf_span[[1, 2]]、#cf_span[[3, 3]]、#cf_span[[3, 4]]。","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, where $ a_i \\in [-10^9, 10^9] $.  \n\nLet $ 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 $.  \n\nLet $ P = \\{ k^m \\mid m \\in \\mathbb{Z}_{\\geq 0} \\} $ be the set of non-negative integer powers of $ k $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq |k| \\leq 10 $  \n3. $ -10^9 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of pairs $ (i,j) $ with $ 1 \\leq i \\leq j \\leq n $ such that $ S(i,j) \\in P $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF776C","tags":["binary search","brute force","data structures","implementation","math"],"sample_group":[["4 2\n2 2 2 2","8"],["4 -3\n3 -6 -3 12","3"]],"created_at":"2026-03-03 11:00:39"}}