A4. Rasta-lover Pair

Codeforces

IDCF10070A4

Time15000ms

Memory1024MB

Difficulty—

English · Original

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]

**Definitions** Let $ n \in \mathbb{Z}^+ $. A pair $ (p, q) $ is **Rasta-lover** if: - $ 1 \leq p, q < n $, - $ \exists x \in \mathbb{Z}^+ $ such that $ p^x \equiv q \pmod{n} $. A number $ p $ is **$ n $-Rastaly** if: - $ 1 \leq p < n $, - $ \gcd(p, n) = 1 $, - $ \exists x \in \mathbb{Z}^+ $ such that $ p^x \equiv 1 \pmod{n} $. Define $ f(n) $ as the smallest positive integer $ a $ such that for every $ n $-Rastaly $ p $, $ p^a \equiv 1 \pmod{n} $. **Constraints** - For subtasks 1–3: Input is $ n $, $ 1 \leq n \leq 10^6 $. - For subtasks 4–6: Input is $ A $, $ 1 \leq A \leq 10^{18} $, and $ M = f(A) $. **Objective** - For subtasks 1–3: Count the number of Rasta-lover pairs modulo $ 10^9 + 7 $. - For subtasks 4–6: Compute $ M = f(A) \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "A4. 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": "CF10070A4"
  },
  "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": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \n\nA pair $ (p, q) $ is **Rasta-lover** if:  \n- $ 1 \\leq p, q < n $,  \n- $ \\exists x \\in \\mathbb{Z}^+ $ such that $ p^x \\equiv q \\pmod{n} $.  \n\nA number $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments