B3. Rasta-making

Codeforces

IDCFB3

Time15000ms

Memory1024MB

Difficulty—

English · Original

Chinese · Translation

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]

给你一个正整数序列。一个正整数序列被称为 #cf_span[Rasta - made]，当且仅当该序列中每两个相邻元素互质。对一个序列进行一次 #cf_span[Rasta - making] 操作，是指选择两个不互质的相邻元素，并将它们同时除以它们的一个公共质因数。例如，我们可以通过一次操作将序列变为。一个序列的 #cf_span[Phoulady] 数是指将其变为 #cf_span[Rasta - made] 序列所需的最少 #cf_span[Rasta - making] 操作次数。一个序列的 #cf_span[Construction] 数是指通过执行 0 次或多次 #cf_span[Rasta - making] 操作所能得到的不同序列的数量。我们用 #cf_span[F] 表示 #cf_span[Phoulady] 数，用 #cf_span[S] 表示 #cf_span[Construction] 数。在所有子任务中：子任务：每个子任务包含一个测试用例。输入包含两个整数 #cf_span[n] 和 #cf_span[M]。请输出答案对 #cf_span[109 + 7] 取模的结果，占一行。 ## Input 每个子任务包含一个测试用例。输入包含两个整数 #cf_span[n] 和 #cf_span[M]。 ## Output 请输出答案对 #cf_span[109 + 7] 取模的结果，占一行。 [samples]

Let $ n, M \in \mathbb{Z}^+ $. Let $ \mathcal{S} $ be the set of all sequences $ a = (a_1, a_2, \dots, a_n) $ of positive integers such that $ 1 \leq a_i \leq M $ for all $ i \in \{1, 2, \dots, n\} $. For a sequence $ a \in \mathcal{S} $, define: - **Rasta-made**: $ a $ is Rasta-made if $ \gcd(a_i, a_{i+1}) = 1 $ for all $ i \in \{1, 2, \dots, n-1\} $. - **Rasta-making operation**: Choose an index $ i \in \{1, 2, \dots, n-1\} $ such that $ \gcd(a_i, a_{i+1}) > 1 $, and choose a prime $ p \mid \gcd(a_i, a_{i+1}) $. Then replace $ a_i \leftarrow a_i / p $, $ a_{i+1} \leftarrow a_{i+1} / p $. - **Phoulady number $ F(a) $**: Minimum number of Rasta-making operations to transform $ a $ into a Rasta-made sequence. - **Construction number $ S(a) $**: Number of distinct sequences obtainable from $ a $ via zero or more Rasta-making operations. Define: - $ F = \sum_{a \in \mathcal{S}} F(a) $ - $ S = \sum_{a \in \mathcal{S}} S(a) $ Compute $ (F + S) \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "B3. 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": "CFB3"
  },
  "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": "给你一个正整数序列。一个正整数序列被称为 #cf_span[Rasta - made]，当且仅当该序列中每两个相邻元素互质。\n\n对一个序列进行一次 #cf_span[Rasta - making] 操作，是指选择两个不互质的相邻元素，并将它们同时除以它们的一个公共质因数。例如，我们可以通过一次操作将序列  变为  。\n\n一个序列的 #cf_span[Phoulady] 数是指将其变为 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n, M \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{S} $ be the set of all sequences $ a = (a_1, a_2, \\dots, a_n) $ of positive integers such that $ 1 \\leq a_i \\leq M $ for all $ i \\in \\{1, 2, \\dots, n\\} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments