OEIS A098928 数表扩充

[A098928](https://oeis.org/A098928)：对 $n\times n\times n$ 的三维立方点阵，问有多少立方体以其格点为顶点。 为了计算这个问题的答案，我们不妨先看看 $2$ 维的情况。我们先考虑一个斜着摆的正方形，其边向量可以写作 $(a,b),(b,-a),(-a,-b),(-b,a)$。考虑这个形状有多少种方法放进 $n\times n$ 的点阵。这取决于它在 $x,y$ 上的长度和宽度。无疑其长宽都是 $a+b$。那么对于被长宽为 $h$ 框住的正方形有 $h$ 种，而这样的正方形有 $(n-h)^2$ 种放法。所以答案就是 $\sum_h h \cdot (n-h)^2$。 对于三维情况，我们发现有一个很大的问题：三个维度的宽度可以是不一样的，比如 $(3,4,0),(4,-3,0),(0,0,5)$ 支成的立方体。我们需要用比较聪明的方法枚举这三条棱。具体来说，需要满足条件： 向量 $\mathbf{u,v,w}$ 两两正交（$\mathbf{u\cdot v = 0}$）且等长 $|\mathbf{u}|=|\mathbf v| = |\mathbf w|$。 对于这样的一组解，它有 $(n - |u_x| - |v_x| - |w_x|) \cdot (n - |u_y| - |v_y| - |w_y|) \cdot (n - |u_z| - |v_z| - |w_z|)$ 种放置方法（前提是各项均 $>0$）。 接 [yhx-12243](https://yhx-12243.github.io/OI-transit/records/cf1375I.html) 的论述，我们知道可以借助 **Hurwitz 四元数** $H=\left\{ s \omega + x \mathrm i + y \mathrm j + z \mathrm k \mid s,x,y,z\in \mathbb Z \right\}, \omega = \frac{1+\mathrm i + \mathrm j + \mathrm k}{2}$ 来枚举这样的向量组。 具体来说，对于每个 $q\in H$，考虑 $v = x \mathrm i + y \mathrm j + z \mathrm k$ 被共轭作用 $v \mapsto qv\overline q$ 确定了一个伸缩旋转。具体来说，首先是进行了旋转 $v \mapsto q v q^{-1}$，然后伸长了 $|qv\overline q| / |v| = |q|^2$ 倍，也就是 $q$ 的范数。但这并没有覆盖所有的变换，再引入无平方因子的奇数 $r$，所有的 $(r,q)$ 构成的 $v \mapsto r\cdot qv\overline q$ 精确覆盖了所有情况。 我们可以直接枚举 $r |q|^2 \le n$ 的 $(r,q)$，由于 $|q|^2\le n$ 的 Hurwitz 四元数只有 $O(n^2)$ 种，那么再枚举 $r$ 之后仍然只有 $\sum_r (n/r)^2 = O(n^2)$ 种。因此枚举的总时间为 $O(n^2)$。（这还是比较反直觉的，因为这说明起手 $O(n^3)$ 枚举其中一条棱的做法走不通！） 这是一份 [代码](https://ideone.com/reAYcy)。加个前缀和优化稍微改改就能在几分钟内跑出 $n\le 10^4$ 的所有答案。 它还有很大的优化空间，因为一个立方体被从每个顶点数了三次，也就是枚举自带了一个 $24$ 倍的常数。这对应于 $|q|=1$ 的 Hurwitz 四元数总共有 $24$ 种。如果能直接在 $H / \{ |\omega|=1\mid \omega\in H\}$ 上枚举就可以去掉这个常数了。[这里](https://www.luogu.com.cn/paste/qn8vpz8u) 是 yhx-12243 优化的版本。