G. Hard Equation

Codeforces

IDCF10185G

Time10000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Consider the following equation Given a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you? The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases. Each test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109). For each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m. If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input. ## Input The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.Each test case consists of a line containing three integers a, b and m (0 ≤ a, b < m ≤ 109). ## Output For each test case, print a single line containing an integer x (0 ≤ x ≤ 1017) that satisfy the equation , for the given a, b and m. If there are multiple solutions, print any of them. It is guaranteed that an answer always exist for the given input. [samples]

**Definitions** Let $ n, t \in \mathbb{Z}^+ $ with $ 1 \leq n, t \leq 2 \times 10^5 $. Let $ \text{id} = (id_1, id_2, \dots, id_n) $ be a sequence of positive integers with $ 1 \leq id_i \leq 5 \times 10^5 $. For each sword $ i $, define its *characteristic set* as: $$ C_i = \{ c \in \mathbb{Z} \mid c > 1 \text{ and } c \mid id_i \} $$ Two swords $ i $ and $ j $ are *compatible* if $ C_i \cap C_j = \emptyset $. Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of swords currently in stock. Initially, $ S = \emptyset $. **Constraints** - Each event updates $ S $: for event $ x $, if $ x \in S $, remove $ x $; else, add $ x $. - After each update, compute the number of unordered pairs $ \{i, j\} \subseteq S $ with $ i \ne j $ and $ C_i \cap C_j = \emptyset $. **Objective** For each of the $ t $ events, output: $$ \left| \left\{ \{i, j\} \subseteq S \mid i \ne j \text{ and } C_i \cap C_j = \emptyset \right\} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "G. Hard Equation",
    "description": {
      "content": "Consider the following equation  Given a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you? The first line contains an integer T (1 ≤ T ≤ 500), in whic",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10185G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following equation \n\nGiven a, b and m, your task is to find a value x that satisfy the equation for the given values. Can you?\n\nThe first line contains an integer T (1 ≤ T ≤ 500), in whic...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, t \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, t \\leq 2 \\times 10^5 $.  \nLet $ \\text{id} = (id_1, id_2, \\dots, id_n) $ be a sequence of positive integers with $ 1 \\leq id_i \\leq 5 \\t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments