D. PolandBall and Polygon

Codeforces

IDCF755D

Time4000ms

Memory256MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

PolandBall has such a convex polygon with _n_ veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments. He chose a number _k_ such that _gcd_(_n_, _k_) = 1. Vertices of the polygon are numbered from 1 to _n_ in a clockwise way. PolandBall repeats the following process _n_ times, starting from the vertex 1: _Assume you've ended last operation in vertex _x_ (consider _x_ = 1 if it is the first operation). Draw a new segment from vertex _x_ to _k_\-th next vertex in clockwise direction. This is a vertex _x_ + _k_ or _x_ + _k_ - _n_ depending on which of these is a valid index of polygon's vertex._ Your task is to calculate number of polygon's sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon's sides. ## Input There are only two numbers in the input: _n_ and _k_ (5 ≤ _n_ ≤ 106, 2 ≤ _k_ ≤ _n_ - 2, _gcd_(_n_, _k_) = 1). ## Output You should print _n_ values separated by spaces. The _i_\-th value should represent number of polygon's sections after drawing first _i_ lines. [samples] ## Note The greatest common divisor (gcd) of two integers _a_ and _b_ is the largest positive integer that divides both _a_ and _b_ without a remainder. For the first sample testcase, you should output "_2 3 5 8 11_". Pictures below correspond to situations after drawing lines. <center>![image](https://espresso.codeforces.com/5a0ddfc15089aaecc7d1e480e9601154d2b69099.png) ![image](https://espresso.codeforces.com/0ea72d36a86cef046b59635f46fdfc22b1ee4cd9.png) ![image](https://espresso.codeforces.com/8fc21e771bfe5ab9fb86edfc389d9e6260b47dea.png) ![image](https://espresso.codeforces.com/8f5aa138efe1a8491385c5aea76cf775c8b87c16.png) ![image](https://espresso.codeforces.com/c2d9279315003b1850365a0f462c45357ba09207.png) ![image](https://espresso.codeforces.com/1749613def8f67efe62bfe0b49500fab680db2bf.png)</center>

[{"iden":"statement","content":"PolandBall 有一个具有 #cf_span[n] 个顶点的凸多边形，且其任意三条对角线都不相交于同一点。PolandBall 决定改进它，画一些红色线段。\n\n他选择了一个数 #cf_span[k]，使得 #cf_span[gcd(n, k) = 1]。多边形的顶点按顺时针方向编号为 #cf_span[1] 到 #cf_span[n]。PolandBall 重复以下过程 #cf_span[n] 次，从顶点 #cf_span[1] 开始：\n\n_假设上一次操作结束于顶点 #cf_span[x]（如果是第一次操作，则视为 #cf_span[x = 1]）。从顶点 #cf_span[x] 向顺时针方向的第 #cf_span[k] 个顶点画一条新线段。这个顶点是 #cf_span[x + k] 或 #cf_span[x + k - n]，取决于哪个是多边形的有效顶点索引。_\n\n你的任务是计算每次画线后多边形被划分出的区域数量。一个区域是指由已画出的对角线或多边形边所围成的清晰内部区域。\n\n输入中仅有两个数字：#cf_span[n] 和 #cf_span[k]（#cf_span[5 ≤ n ≤ 106]，#cf_span[2 ≤ k ≤ n - 2]，#cf_span[gcd(n, k) = 1]）。\n\n你需要输出 #cf_span[n] 个用空格分隔的数值。第 #cf_span[i] 个值应表示画完前 #cf_span[i] 条线后多边形的区域数量。\n\n两个整数 #cf_span[a] 和 #cf_span[b] 的最大公约数（gcd）是指能同时整除 #cf_span[a] 和 #cf_span[b] 且无余数的最大正整数。\n\n对于第一个样例测试用例，你应该输出 \"_2 3 5 8 11_\"。下图对应于画线后的各个状态。"}, {"iden":"input","content":"输入中仅有两个数字：#cf_span[n] 和 #cf_span[k]（#cf_span[5 ≤ n ≤ 106]，#cf_span[2 ≤ k ≤ n - 2]，#cf_span[gcd(n, k) = 1]）。"}, {"iden":"output","content":"你应该输出 #cf_span[n] 个用空格分隔的数值。第 #cf_span[i] 个值应表示画完前 #cf_span[i] 条线后多边形的区域数量。"}, {"iden":"examples","content":"输入\n5 2\n输出\n2 3 5 8 11\n\n输入\n10 3\n输出\n2 3 4 6 9 12 16 21 26 31 "}, {"iden":"note","content":"两个整数 #cf_span[a] 和 #cf_span[b] 的最大公约数（gcd）是指能同时整除 #cf_span[a] 和 #cf_span[b] 且无余数的最大正整数。对于第一个样例测试用例，你应该输出 \"_2 3 5 8 11_\"。下图对应于画线后的各个状态。 "}]"

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 5 \leq n \leq 10^6 $, $ 2 \leq k \leq n-2 $, and $ \gcd(n, k) = 1 $. Let $ V = \{1, 2, \dots, n\} $ be the set of polygon vertices labeled clockwise. Let $ S_i $ be the set of line segments drawn after $ i $ steps, where the $ j $-th segment connects vertex $ x_j $ to vertex $ x_j + k \pmod{n} $, starting from $ x_1 = 1 $, and $ x_j = x_{j-1} + k \pmod{n} $ for $ j \geq 2 $. **Constraints** 1. $ \gcd(n, k) = 1 $ 2. All indices are taken modulo $ n $, with representatives in $ \{1, 2, \dots, n\} $ 3. The polygon is convex, and no three diagonals intersect at a single interior point. **Objective** For each $ i \in \{1, 2, \dots, n\} $, compute $ f(i) $, the number of regions (connected components) formed inside the polygon by the first $ i $ segments. Output: $ f(1), f(2), \dots, f(n) $

Samples

Input #1

5 2

Output #1

2 3 5 8 11

Input #2

10 3

Output #2

2 3 4 6 9 12 16 21 26 31

API Response (JSON)

{
  "problem": {
    "name": "D. PolandBall and Polygon",
    "description": {
      "content": "PolandBall has such a convex polygon with _n_ veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments. He chose a number _k_ s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF755D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PolandBall has such a convex polygon with _n_ veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments.\n\nHe chose a number _k_ s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"PolandBall 有一个具有 #cf_span[n] 个顶点的凸多边形，且其任意三条对角线都不相交于同一点。PolandBall 决定改进它，画一些红色线段。\\n\\n他选择了一个数 #cf_span[k]，使得 #cf_span[gcd(n, k) = 1]。多边形的顶点按顺时针方向编号为 #cf_span[1] 到 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 5 \\leq n \\leq 10^6 $, $ 2 \\leq k \\leq n-2 $, and $ \\gcd(n, k) = 1 $.  \nLet $ V = \\{1, 2, \\dots, n\\} $ be the set of polygon vertices labeled clockw...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments