{"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_ 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:\n\n_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._\n\nYour 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.\n\n## Input\n\nThere are only two numbers in the input: _n_ and _k_ (5 ≤ _n_ ≤ 106, 2 ≤ _k_ ≤ _n_ - 2, _gcd_(_n_, _k_) = 1).\n\n## Output\n\nYou should print _n_ values separated by spaces. The _i_\\-th value should represent number of polygon's sections after drawing first _i_ lines.\n\n[samples]\n\n## Note\n\nThe greatest common divisor (gcd) of two integers _a_ and _b_ is the largest positive integer that divides both _a_ and _b_ without a remainder.\n\nFor the first sample testcase, you should output \"_2 3 5 8 11_\". Pictures below correspond to situations after drawing lines.\n\n<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>","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_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_\\\"。下图对应于画线后的各个状态。       \"}]\"","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 clockwise.  \nLet $ 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 $.  \n\n**Constraints**  \n1. $ \\gcd(n, k) = 1 $  \n2. All indices are taken modulo $ n $, with representatives in $ \\{1, 2, \\dots, n\\} $  \n3. The polygon is convex, and no three diagonals intersect at a single interior point.  \n\n**Objective**  \nFor 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.  \n\nOutput: $ f(1), f(2), \\dots, f(n) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF755D","tags":["data structures"],"sample_group":[["5 2","2 3 5 8 11"],["10 3","2 3 4 6 9 12 16 21 26 31"]],"created_at":"2026-03-03 11:00:39"}}