A3. Rasta-lover Pair

Codeforces

IDCFA3

Time15000ms

Memory1024MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that: px ≡ q (modn) Subtasks 1 - 3: Given n, calculate the number of Rasta - lover pairs modulo 109 + 7. Subtasks 4 - 6: A positive integer p is called n - Rastaly if and only if p < n and there is a positive integer like x such that px ≡ 1 (modn) and p and n are coprimes. For a positive integer n, f(n) is the smallest positive integer a such that for each n - Rastaly number like p, pa ≡ 1 (modn) (this number always exists). If M is equal to for a given A, then you have to calculate M modulo 109 + 7. Subtasks: Each subtask consists of one testcase. Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A. Print the answer modulo 109 + 7 in one line. ## Input Each subtask consists of one testcase.Input consists of one number. For subtasks 1-3, it's n and for subtasks 4-6 it's A. ## Output Print the answer modulo 109 + 7 in one line. [samples]

一对整数 #cf_span[(p, q)] 被称为 #cf_span[Rasta - lover]，当且仅当 #cf_span[1 ≤ p, q < n] 且存在一个正整数 #cf_span[x] 使得： #cf_span[px ≡ q] #cf_span[(modn)] 子任务 #cf_span[1 - 3]：给定 #cf_span[n]，计算 #cf_span[Rasta - lover] 对的数量，对 #cf_span[109 + 7] 取模。子任务 #cf_span[4 - 6]：一个正整数 #cf_span[p] 被称为 #cf_span[n - Rastaly]，当且仅当 #cf_span[p < n] 且存在一个正整数 #cf_span[x] 使得 #cf_span[px ≡ 1] #cf_span[(modn)]，且 #cf_span[p] 与 #cf_span[n] 互质。对于正整数 #cf_span[n]，#cf_span[f(n)] 是最小的正整数 #cf_span[a]，使得对每个 #cf_span[n - Rastaly] 数 #cf_span[p]，都有 #cf_span[pa ≡ 1] #cf_span[(modn)]（这样的数总是存在）。如果给定 #cf_span[A] 时 #cf_span[M] 等于，则你需要计算 #cf_span[M] 对 #cf_span[109 + 7] 取模的结果。子任务：每个子任务包含一个测试用例。输入包含一个数。对于子任务 1-3，该数为 #cf_span[n]；对于子任务 4-6，该数为 #cf_span[A]。请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。 ## Input 每个子任务包含一个测试用例。输入包含一个数。对于子任务 1-3，该数为 #cf_span[n]；对于子任务 4-6，该数为 #cf_span[A]。 ## Output 请在一行中输出答案对 #cf_span[109 + 7] 取模的结果。 [samples]

**Definitions:** - Let $ n \in \mathbb{Z}^+ $. - Let $ \mathbb{Z}_n^* = \{ p \in \mathbb{Z} : 1 \leq p < n, \gcd(p, n) = 1 \} $ be the multiplicative group modulo $ n $. - Let $ \lambda(n) $ denote the Carmichael function: the smallest positive integer $ a $ such that $ p^a \equiv 1 \pmod{n} $ for all $ p \in \mathbb{Z}_n^* $. --- **Subtasks 1–3:** Count the number of pairs $ (p, q) \in \mathbb{Z}^2 $ such that: - $ 1 \leq p, q < n $, - $ \exists x \in \mathbb{Z}^+ $ such that $ p^x \equiv q \pmod{n} $. Let $ S(n) = \left| \left\{ (p, q) \in [1, n-1]^2 : \exists x \geq 1 \text{ s.t. } p^x \equiv q \pmod{n} \right\} \right| $. Compute $ S(n) \mod (10^9 + 7) $. --- **Subtasks 4–6:** Given $ A \in \mathbb{Z}^+ $, compute $ f(n) = \lambda(n) $, where $ n $ is the unique positive integer such that $ \lambda(n) = A $. If no such $ n $ exists, the problem is undefined — but the input guarantees existence. Compute $ A \mod (10^9 + 7) $. > **Note:** The problem states: > *“If $ M $ is equal to for a given $ A $, then you have to calculate $ M $ modulo $ 10^9 + 7 $.”* > This is malformed, but context implies $ M = \lambda(n) = A $, so we are to output $ A \mod (10^9 + 7) $. --- **Final Formal Output:** For input $ n $ (subtasks 1–3): $$ \boxed{S(n) = \left| \left\{ (p, q) \in [1, n-1]^2 : \exists x \in \mathbb{Z}^+,\ p^x \equiv q \pmod{n} \right\} \right| \mod (10^9 + 7)} $$ For input $ A $ (subtasks 4–6): $$ \boxed{A \mod (10^9 + 7)} $$

API Response (JSON)

{
  "problem": {
    "name": "A3. Rasta-lover Pair",
    "description": {
      "content": "A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that: px ≡ q (modn) Subtasks 1 - 3:  Given n, calculate the number o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CFA3"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A pair (p, q) of integer numbers is called Rasta - lover if and only if 1 ≤ p, q < n and there is a positive integer like x such that:\n\npx ≡ q (modn)\n\nSubtasks 1 - 3: \n\nGiven n, calculate the number o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一对整数 #cf_span[(p, q)] 被称为 #cf_span[Rasta - lover]，当且仅当 #cf_span[1 ≤ p, q < n] 且存在一个正整数 #cf_span[x] 使得：\n\n#cf_span[px ≡ q] #cf_span[(modn)]\n\n子任务 #cf_span[1 - 3]：\n\n给定 #cf_span[n]，计算 #cf_span[Rasta - love...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\n- Let $ n \\in \\mathbb{Z}^+ $.\n- Let $ \\mathbb{Z}_n^* = \\{ p \\in \\mathbb{Z} : 1 \\leq p < n, \\gcd(p, n) = 1 \\} $ be the multiplicative group modulo $ n $.\n- Let $ \\lambda(n) $ denote t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments