HyperKnight

作者：毛啸

关键词：枚举 排序

题目简述

移动方式$(u, v)$的定义是假如你当前在$(x, y)$，那么你将移动到$(x + u, y + v)$，给定$a, b$，你的移动方式有$(a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)$八种。如果你从当前格子进行某个移动之后仍然在棋盘内，那么这个移动方式就被称为合法的。

给定一个$n \times m$的棋盘，以及一个0到8之间的数$k$，求恰好有$k$种合法移动方式的格子数。

$n, m, a, b \le 10 ^ 9$。

一种常见的思考方式

我们经常会遇到一类问题，给你一个非常大的集合，问你有多少个元素满足某个条件。

那么，一个常见的思考方式是，我们可以把集合用一些子集划分，并且子集的数量不多，并且 每个子集中的元素要么同时满足条件，要么同时不满足。

算法

那么本题可以怎么划分呢？我们注意到，某种移动方式是否合法，可以表示成一系列关于坐标$(x, y)$的不等式，而不等式的解总是$x \le X$或$x \ge X$，其中$X \in \{a, b, n - a, n - b\}$，或者$y \le Y$或$y \ge Y$，其中$Y \in \{a, b, m - a, m - b\}$。

于是，我们就按照这些值划分$x$轴和$y$轴，对于每一个$x$轴的区间和$y$轴的区间，它们所对应的矩形区域对应的合法移动方式种类是一样的，我们只需要检查移动方式的数量是否等于$k$，如果等于$k$，就将答案加上矩形区域的大小即可。

时空复杂度均为$O(1)$。

易错点

注意答案要用64位整形存储，注意整形溢出问题。

注意$a$和$b$以及$n$和$m$不要打反。