I. From Modular to Rational

Codeforces

IDCF10235I

Time6000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_This is an interactive problem._ Someone picked a positive rational number $x = p \/ q$ where $1 <= p, q <= 10^9$. You may ask at most $10$ queries of the kind "_? $m$_", where $10^9 < m < 10^(12)$ and $m$ is a prime number. For each query, you will get the number $y$ such that $y equiv p q^(-1) pmod m$. You have to guess the number $x$. The first line of input contains a single integer $t$, the number of test cases ($1 <= t <= 10^5$). For each test case, you may ask at most $10$ queries. Each query should be one of two types: In the example, you deal with $x = 1 \/ 1$, $x = 1 \/ 2$, and $x = 2 \/ 1$, while always taking $m = 10^9 + 7$. As you may see, it is not necessary to have $gcd (p, q) = 1$ as long as $1 <= p, q <= 10^9$ and $x = p \/ q$. ## Interaction The first line of input contains a single integer $t$, the number of test cases ($1 <= t <= 10^5$).For each test case, you may ask at most $10$ queries. Each query should be one of two types: "_? $m$_", where $10^9 < m < 10^(12)$ and $m$ is a prime number, "_! $p$ $q$_", where $1 <= p, q <= 10^9$, meaning that the answer is equal to $p \/ q$. It is guaranteed that the number $x$ in each test case does not change during testing. [samples] ## Note In the example, you deal with $x = 1 \/ 1$, $x = 1 \/ 2$, and $x = 2 \/ 1$, while always taking $m = 10^9 + 7$. As you may see, it is not necessary to have $gcd (p, q) = 1$ as long as $1 <= p, q <= 10^9$ and $x = p \/ q$.

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case, an unknown rational number $ x = \frac{p}{q} \in \mathbb{Q} $ is fixed, with $ p, q \in \mathbb{Z} $, $ 1 \leq p, q \leq 10^9 $. **Constraints** 1. $ 1 \leq t \leq 10^5 $ 2. For each test case, at most $ 10 $ queries are allowed. 3. Each query specifies a prime modulus $ m $ such that $ 10^9 < m < 10^{12} $. 4. For each query $ m $, the response is $ y \equiv p \cdot q^{-1} \pmod{m} $, where $ q^{-1} $ denotes the modular inverse of $ q $ modulo $ m $. **Objective** Reconstruct the unique rational number $ x = \frac{p}{q} $ satisfying $ 1 \leq p, q \leq 10^9 $, using at most 10 modular queries per test case.

API Response (JSON)

{
  "problem": {
    "name": "I. From Modular to Rational",
    "description": {
      "content": "_This is an interactive problem._ Someone picked a positive rational number $x = p \\/ q$ where $1 <= p, q <= 10^9$. You may ask at most $10$ queries of the kind \"_? $m$_\", where $10^9 < m < 10^(12)$ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10235I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_This is an interactive problem._\n\nSomeone picked a positive rational number $x = p \\/ q$ where $1 <= p, q <= 10^9$. You may ask at most $10$ queries of the kind \"_? $m$_\", where $10^9 < m < 10^(12)$ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, an unknown rational number $ x = \\frac{p}{q} \\in \\mathbb{Q} $ is fixed, with $ p, q \\in \\mathbb{Z} $, $ 1 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments