B2. Rasta-making

Codeforces

IDCF10070B2

Time15000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Sequence of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other. A Rasta - making operation on a sequence consists of choosing two non-coprime consecutive elements from it and divide them both by one of their common prime factors. For example, we can turn the seqeunce to with performing one operation. Phoulady number of a sequence is the minimum number of Rasta - making operations needed for turning it into a Rasta - made sequence. Construction number of a a sequence is the number of different sequences we can get by performing 0 or more Rasta - making operations. We show Phoulady number by F and Construction number by S. In all subtasks: Subtasks: Each subtask consists of one testcase. Input consists of two integers, n and M. Print the answer modulo 109 + 7 in a single line. ## Input Each subtask consists of one testcase.Input consists of two integers, n and M. ## Output Print the answer modulo 109 + 7 in a single line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ M \in \mathbb{Z}^+ $. Let $ \mathcal{A} = \{ (a_1, \dots, a_n) \in \{1, \dots, M\}^n \} $ be the set of all sequences of length $ n $ with positive integers $ \leq M $. A sequence $ A = (a_1, \dots, a_n) \in \mathcal{A} $ is **#cf_span[Rasta-made]** if $ \gcd(a_i, a_{i+1}) = 1 $ for all $ i \in \{1, \dots, n-1\} $. A **#cf_span[Rasta-making] operation** on $ A $ at position $ i $ (where $ \gcd(a_i, a_{i+1}) > 1 $) selects a prime $ p \mid \gcd(a_i, a_{i+1}) $, and replaces $ (a_i, a_{i+1}) $ with $ \left( \frac{a_i}{p}, \frac{a_{i+1}}{p} \right) $. Let $ F(A) $ be the **#cf_span[Phoulady] number** of $ A $: the minimum number of #cf_span[Rasta-making] operations to make $ A $ #cf_span[Rasta-made]. Let $ S(A) $ be the **#cf_span[Construction] number** of $ A $: the number of distinct #cf_span[Rasta-made] sequences reachable from $ A $ via any number of #cf_span[Rasta-making] operations. **Constraints** $ 1 \leq n \leq 50 $, $ 1 \leq M \leq 10^5 $. **Objective** Compute: $$ \sum_{A \in \mathcal{A}} F(A) \cdot S(A) \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "B2. Rasta-making",
    "description": {
      "content": "Sequence  of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other.  A ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10070B2"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sequence  of positive integers is given to you. A sequence of positive integers is called Rasta - made if and only if every two consecutive elements from this sequence are coprimes to each other. \n\nA ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{A} = \\{ (a_1, \\dots, a_n) \\in \\{1, \\dots, M\\}^n \\} $ be the set of all sequences of length $ n $ with positive in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments