← 返回题目列表

Codeforces · 755/D

D. 波兰球和多边形

中文机器翻译题面 查看原题

波兰球有一个具有 n 个顶点的凸多边形,其任何三个对角线都不相交于同一点。波兰球决定对其进行改进并绘制一些红色部分。

他选择了一个数字 k,使得 gcd(n, k) = 1。多边形的顶点按顺时针方向从 1 到 n 编号。波兰球从顶点 1 开始重复以下过程 n 次:

假设您已结束顶点 x 中的最后一个操作(如果是第一个操作,则考虑 x = 1)。沿顺时针方向从顶点 x 到下一个顶点绘制一条新线段。这是顶点 x + k 或 x + k - n ,具体取决于其中哪一个是多边形顶点的有效索引。

您的任务是在每次绘制后计算多边形的截面数。截面是多边形内部以绘制的对角线或多边形的边为界的清晰区域。

输入

输入中只有两个数字:n 和 k (5 ≤ n ≤ 106, 2 ≤ k ≤ n - 2, gcd(n, k) = 1)。

输出

您应该打印 n 个值,并用空格分隔。第 i 个值应表示绘制前 i 条线后多边形的截面数。

示例

输入 #1

5 2

输出 #1

2 3 5 8 11

输入 #2

10 3

输出 #2

2 3 4 6 9 12 16 21 26 31

注意

两个整数 a 和 b 的最大公约数 (gcd) 是同时整除 a 和 b 且无余数的最大正整数。

对于第一个示例测试用例,您应该输出“2 3 5 8 11”。下图对应画线后的情况。