B. Stars

Codeforces

IDCF10238B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

On Planet E, there are many stars! To be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($(x, y)$ where both $x$ and $y$ are integers). People on Planet E have a hobby of drawing straight segments between the stars. One day, they are curious about how many stars their straight segments have covered. Can you help the people on Planet E to count the number of stars on their straight segments? The first line contains a positive integer $T$ ($T <= 100$), the number of testcases. Each testcase contains 4 integers $x_0, y_0, x_1, y_1$ ($| x_i | <= 10^9$ and $| y_i | <= 10^9$ for $i = 0, 1$), representing the segment $(x_0, y_0)$ to $(x_1, y_1)$. For each testcase, output a single line consisting of the number of stars on the segment. In the first testcase, the only covered star is $(1, 1)$. In the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$. ## Input The first line contains a positive integer $T$ ($T <= 100$), the number of testcases.Each testcase contains 4 integers $x_0, y_0, x_1, y_1$ ($| x_i | <= 10^9$ and $| y_i | <= 10^9$ for $i = 0, 1$), representing the segment $(x_0, y_0)$ to $(x_1, y_1)$. ## Output For each testcase, output a single line consisting of the number of stars on the segment. [samples] ## Note In the first testcase, the only covered star is $(1, 1)$.In the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$.

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ P_k = (x_0^{(k)}, y_0^{(k)}) $ and $ Q_k = (x_1^{(k)}, y_1^{(k)}) $ be the endpoints of a line segment in $ \mathbb{Z}^2 $. **Constraints** 1. $ 1 \le T \le 100 $ 2. $ |x_i^{(k)}| \le 10^9 $, $ |y_i^{(k)}| \le 10^9 $ for $ i \in \{0,1\} $, $ k \in \{1, \dots, T\} $ **Objective** For each test case $ k $, compute the number of lattice points (stars) on the closed line segment from $ P_k $ to $ Q_k $: $$ \gcd(|x_1^{(k)} - x_0^{(k)}|, |y_1^{(k)} - y_0^{(k)}|) + 1 $$

API Response (JSON)

{
  "problem": {
    "name": "B. Stars",
    "description": {
      "content": "On Planet E, there are many stars! To be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($(x, y)$ where both $x$ and $y$ are integers). People on Pla",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10238B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On Planet E, there are many stars!\n\nTo be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($(x, y)$ where both $x$ and $y$ are integers).\n\nPeople on Pla...",
      "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 $ k \\in \\{1, \\dots, T\\} $, let $ P_k = (x_0^{(k)}, y_0^{(k)}) $ and $ Q_k = (x_1^{(k)}, y_1^{(k)}) $ be t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments