E. Card Game Again

Codeforces

IDCF818E

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresnumber theorytwo pointers

English · Original

Chinese · Translation

Formal · Original

Vova again tries to play some computer card game. The rules of deck creation in this game are simple. Vova is given an existing deck of _n_ cards and a magic number _k_. The order of the cards in the deck is fixed. Each card has a number written on it; number _a__i_ is written on the _i_\-th card in the deck. After receiving the deck and the magic number, Vova removes _x_ (possibly _x_ = 0) cards from the top of the deck, _y_ (possibly _y_ = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards _x_ + 1, _x_ + 2, ... _n_ - _y_ - 1, _n_ - _y_ from the original deck. Vova's new deck is considered _valid_ iff the product of all numbers written on the cards in his new deck is divisible by _k_. So Vova received a deck (possibly not a _valid_ one) and a number _k_, and now he wonders, how many ways are there to choose _x_ and _y_ so the deck he will get after removing _x_ cards from the top and _y_ cards from the bottom is _valid_? ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _k_ ≤ 109). The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the numbers written on the cards. ## Output Print the number of ways to choose _x_ and _y_ so the resulting deck is _valid_. [samples] ## Note In the first example the possible values of _x_ and _y_ are: 1. _x_ = 0, _y_ = 0; 2. _x_ = 1, _y_ = 0; 3. _x_ = 2, _y_ = 0; 4. _x_ = 0, _y_ = 1.

Vova 再次尝试玩一款电脑卡牌游戏。该游戏中的牌组创建规则很简单。Vova 被给予一个包含 #cf_span[n] 张牌的现有牌组和一个魔法数字 #cf_span[k]。牌组中牌的顺序是固定的，每张牌上写有一个数字；第 #cf_span[i] 张牌上写的数字是 #cf_span[ai]。在收到牌组和魔法数字后，Vova 会从牌组顶部移除 #cf_span[x] 张牌（可能 #cf_span[x = 0]），从牌组底部移除 #cf_span[y] 张牌（可能 #cf_span[y = 0]），剩余的牌组即为他的新牌组（移除后必须至少保留一张牌）。因此，Vova 的新牌组实际上包含原牌组中的第 #cf_span[x + 1]、#cf_span[x + 2]、...、#cf_span[n - y - 1]、#cf_span[n - y] 张牌。当新牌组中所有牌上数字的乘积能被 #cf_span[k] 整除时，该牌组被认为是 _合法的_。因此，Vova 得到了一个牌组（可能不是 _合法的_）和一个数字 #cf_span[k]，现在他想知道，有多少种选择 #cf_span[x] 和 #cf_span[y] 的方式，使得移除 #cf_span[x] 张顶部牌和 #cf_span[y] 张底部牌后得到的牌组是 _合法的_？第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ k ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 10^9]）——写在牌上的数字。请输出选择 #cf_span[x] 和 #cf_span[y] 使得结果牌组 _合法_ 的方式数量。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ k ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1]、#cf_span[a2]、...、#cf_span[an]（#cf_span[1 ≤ ai ≤ 10^9]）——写在牌上的数字。 ## Output 请输出选择 #cf_span[x] 和 #cf_span[y] 使得结果牌组 _合法_ 的方式数量。 [samples] ## Note 在第一个例子中，#cf_span[x] 和 #cf_span[y] 的可能取值为：#cf_span[x = 0, y = 0]；#cf_span[x = 1, y = 0]；#cf_span[x = 2, y = 0]；#cf_span[x = 0, y = 1]。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 10^5 $, $ 1 \leq k \leq 10^9 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ 1 \leq a_i \leq 10^9 $. Let $ x, y \in \mathbb{Z} $ denote the number of cards removed from the top and bottom, respectively, such that $ x \geq 0 $, $ y \geq 0 $, and $ x + y < n $ (so at least one card remains). The resulting deck is the contiguous subsequence $ A[x+1 : n-y] = (a_{x+1}, a_{x+2}, \dots, a_{n-y}) $. **Constraints** 1. $ 0 \leq x \leq n-1 $ 2. $ 0 \leq y \leq n-1 $ 3. $ x + y \leq n - 1 $ **Objective** Count the number of pairs $ (x, y) $ such that the product $ P = \prod_{i=x+1}^{n-y} a_i $ satisfies $ k \mid P $.

Samples

Input #1

3 4
6 2 8

Output #1

Input #2

3 6
9 1 14

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Card Game Again",
    "description": {
      "content": "Vova again tries to play some computer card game. The rules of deck creation in this game are simple. Vova is given an existing deck of _n_ cards and a magic number _k_. The order of the cards in the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF818E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vova again tries to play some computer card game.\n\nThe rules of deck creation in this game are simple. Vova is given an existing deck of _n_ cards and a magic number _k_. The order of the cards in the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vova 再次尝试玩一款电脑卡牌游戏。\n\n该游戏中的牌组创建规则很简单。Vova 被给予一个包含 #cf_span[n] 张牌的现有牌组和一个魔法数字 #cf_span[k]。牌组中牌的顺序是固定的，每张牌上写有一个数字；第 #cf_span[i] 张牌上写的数字是 #cf_span[ai]。\n\n在收到牌组和魔法数字后，Vova 会从牌组顶部移除 #cf_span[x] 张牌（可能 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq k \\leq 10^9 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ 1 \\leq a_i \\leq 10^9 $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments