A16508 | $Onion$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

洋葱在世界各地的美食中被广泛使用。本题讨论的是几何中的“洋葱剥皮”过程。 在二维平面中，一组点是凸的，如果对于集合中的任意两点 $p$ 和 $q$，连接 $p$ 和 $q$ 的线段都完全包含在该集合中。对于一组点 $S$，它的凸包是包含 $S$ 的最小的凸集。 给定四个整数 $n$、$a$、$b$ 和 $k$。你有一个初始包含 $n$ 个点的集合 $S$，定义如下： $$ S = \{ (x, (a x + b) \bmod n) \mid x = 0, 1, \ldots, n-1 \}。 $$ 你要进行如下操作 $k$ 次：令 $H$ 为集合 $S$ 的凸包，然后将 $S$ 中所有在 $H$ 的边界上的点都从 $S$ 中移除。 注意，$S$ 可能会变为空集。在这种情况下，它的凸包也是空的，面积为零。 对于每一次操作，输出相应的凸包 $H$ 的面积的两倍。可以证明，这个结果总是整数。

输入包含一行，四个整数 $n$、$a$、$b$ 和 $k$，满足 $1 \le n \le 10^9$，$0 \le a, b < n$，$1 \le k \le 300$。

输出 $k$ 行，第 $i$ 行为第 $i$ 次操作后的凸包的面积的两倍。

输入 #1

4 1 2 1

输出 #1

C++ 编辑器

输入

输出