{"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 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.\n\nCan you help the people on Planet E to count the number of stars on their straight segments?\n\nThe first line contains a positive integer $T$ ($T <= 100$), the number of testcases.\n\nEach 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)$.\n\nFor each testcase, output a single line consisting of the number of stars on the segment.\n\nIn the first testcase, the only covered star is $(1, 1)$.\n\nIn the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$.\n\n## Input\n\nThe 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)$.\n\n## Output\n\nFor each testcase, output a single line consisting of the number of stars on the segment.\n\n[samples]\n\n## Note\n\nIn the first testcase, the only covered star is $(1, 1)$.In the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$.","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 the endpoints of a line segment in $ \\mathbb{Z}^2 $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ |x_i^{(k)}| \\le 10^9 $, $ |y_i^{(k)}| \\le 10^9 $ for $ i \\in \\{0,1\\} $, $ k \\in \\{1, \\dots, T\\} $\n\n**Objective**  \nFor each test case $ k $, compute the number of lattice points (stars) on the closed line segment from $ P_k $ to $ Q_k $:  \n$$\n\\gcd(|x_1^{(k)} - x_0^{(k)}|, |y_1^{(k)} - y_0^{(k)}|) + 1\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10238B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}