G. Baby Ehab and a GCD Problem, Of Course

Codeforces

IDCF10288G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Ehab the baby was playing with special cubes that had numbers written on them. Every while, Baby Badawy, who envied Ehab for being younger than him, would throw all the cubes with numbers between a pair of numbers ($l$ and $r$) he chose on Baby Ehab. Every time Badawy threw cubes on Ehab, Ehab would just add them to his cubes, calculate the $G C D$ of the numbers written on *all* of the cubes he has so far, and write the result on a piece of paper. Note that the $G C D$ of a sequence of numbers is the greatest number that divides all of them. Can you guess the numbers Ehab wrote knowing which cubes Badawy threw each time? The first line contains a single integer $q$ $(1 <= q <= 10^5)$ — the number of times Badawy threw cubes on Ehab. Each of the following $q$ lines will contain two integers $l_i$ and $r_i$ $(1 <= l_i <= r_i <= 10^(18))$ — meaning that for each number between $l_i$ and $r_i$ (inclusive), Badawy will throw a cube on Ehab with that number written on it. Output $q$ integers each on a single line — the numbers that Ehab wrote down. ## Input The first line contains a single integer $q$ $(1 <= q <= 10^5)$ — the number of times Badawy threw cubes on Ehab.Each of the following $q$ lines will contain two integers $l_i$ and $r_i$ $(1 <= l_i <= r_i <= 10^(18))$ — meaning that for each number between $l_i$ and $r_i$ (inclusive), Badawy will throw a cube on Ehab with that number written on it. ## Output Output $q$ integers each on a single line — the numbers that Ehab wrote down. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of line segments. For each $ i \in \{1, \dots, n\} $, let $ L_i $ be a line segment in $ \mathbb{R}^2 $ with endpoints $ (x_{i1}, y_{i1}) $ and $ (x_{i2}, y_{i2}) $. Let $ P_i \subseteq \mathbb{R}^2 $ be the set of all points on $ L_i $, i.e., $$ P_i = \{ (1 - t) \cdot (x_{i1}, y_{i1}) + t \cdot (x_{i2}, y_{i2}) \mid t \in [0, 1] \}. $$ Let $ \mathcal{P} = P_1 \times P_2 \times \cdots \times P_n $ be the set of all possible selections of one point per segment. For any $ \mathbf{p} = (p_1, \dots, p_n) \in \mathcal{P} $, define the *odd point* as: $$ S(\mathbf{p}) = \sum_{i=1}^n p_i \in \mathbb{R}^2. $$ **Objective** Compute: $$ \max_{\mathbf{p}, \mathbf{q} \in \mathcal{P}} \| S(\mathbf{p}) - S(\mathbf{q}) \|^2. $$ If $ |\mathcal{P}| = 1 $, output $ 0 $.

API Response (JSON)

{
  "problem": {
    "name": "G. Baby Ehab and a GCD Problem, Of Course",
    "description": {
      "content": "Ehab the baby was playing with special cubes that had numbers written on them. Every while, Baby Badawy, who envied Ehab for being younger than him, would throw all the cubes with numbers between a p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10288G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ehab the baby was playing with special cubes that had numbers written on them.\n\nEvery while, Baby Badawy, who envied Ehab for being younger than him, would throw all the cubes with numbers between a p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of line segments.  \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ L_i $ be a line segment in $ \\mathbb{R}^2 $ with endpoints $ (x_{i1}, y_{i1}) $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments