题目在此 | C++ 标程在此 | Haskell 标程在此

（求 dalao 拍啊，我不知道有没有写对啊。）

这题标解是数论，checker 是计算几何……

时限高于 Haskell 两倍应该算不卡常了吧。

简要题面

在平面直角坐标系中，你可以每次选择两个格点（$(x,y)$，其中 $x$ 和 $y$ 都是整数的点），然后做出过这两个点的直线。

画出四条这样的直线，可以围成一个正方形，这个正方形具有面积 $S$。

给定面积有理数 $S = p / q$，是否存在一种方案能围出这个正方形？如果是，请给出一种构造。

暴力解法

不会！

真的，我不会！

我完全不知道有什么 10 分提答的和 40 分暴力的解法……

我不知道有没有人从提答点里看出什么： $$ \begin{array}{rcl} 4999889 &=& 4999889^{1}\\ 3988009 &=& 1997^{2}\\ 4012009 &=& 2003^{2}\\ 4999762 &=& 2^{1} \times 2499881^{1}\\ 3674633 &=& 1901^{1} \times 1933^{1}\\ 4999348 &=& 2^{2} \times 1249837^{1}\\ 4997709 &=& 3^{2} \times 555301^{1}\\ 2000066 &=& 2^{1} \times 1000033^{1}\\ 4782969 &=& 3^{14}\\ 1953125 &=& 5^{9}\\ \end{array} $$

正解

这题看着就不像有什么几何意义，我们来算一波。

直线

既然都是整点连出的直线，那么显然，画出的直线都是这个形式的： $$ Ax+By+C=0 \quad (A,B,C\in \mathbb{Q},\ A^2 + B^2 \neq 0) $$ 乘分母，得 $$ Ax + By + C = 0 \quad (A,B,C\in\mathbb{Z},\ A^2 + B^2 \neq 0) $$ 只要这个直线经过一个整点 $(x_0, y_0)$，那么也会经过 $(x_0 - B, y_0 + A)$。根据 Bezout 等式（俗称 exgcd），我们知道，上述方程有整数解当且仅当 $\gcd(A,B) \mid C$。等式两边除以 $\gcd(A,B)$ 得直线可以画出的充分必要条件为： $$ Ax+By+C=0 \quad (A,B,C \in \mathbb{Z},\ \gcd(A,B)=1) $$

正方形

我们肯定要画两对平行线，且这两对之间垂直。不妨设为： $$ \begin{array}{rcl} Ax+By+C_1 &=& 0 \\ Ax+By+C_2 &=& 0 \\ Bx-Ay+C_3 &=& 0 \\ Bx-Ay+C_4 &=& 0 \\ \end{array} $$ 平行线间距离应该相等，且等于正方形边长： $$ \sqrt{S} = {|C_2 - C_1| \over \sqrt{A^2 + B^2}}={|C_4 - C_3| \over \sqrt{A^2+B^2}} $$ 因为只要 $\gcd(A,B)=1$，四个 $C$ 是可以随便取的，不妨取 $C_1 = C_2 = 0$ 和 $C_3 = C_4 = C$，则： $$ \begin{array}{rcl} Ax+By& &=& 0 \\ Ax+By& +\ C &=& 0 \\ Bx-Ay& &=& 0 \\ Bx-Ay&+\ C &=& 0 \\ \end{array} $$ 因此要构造四条直线等价于构造 $A,B,C$ 使得：

$$ S = {C^2 \over A^2 + B^2} \quad (\gcd(A,B)=1) $$ 得到 $A,B,C$ 后，就可以用 exgcd 算出四条直线需要经过的格点。以 $Ax+By+C=0$ 为例，用 exgcd 得到 $u,v$ 使 $Au+Bv=1$，则只需画过 $(-uC, -vC)$ 和 $(-uC - B, -vC + A)$ 的直线。

平方和 $A^2 + B^2$

$i = \sqrt{-1}$ 是虚数单位。

考虑上边那个 $S$ 的式子里面的分母 $K$，注意到： $$ K=A^2+B^2=(A+Bi)(A-Bi) $$ 有个东西叫做**高斯整数**，指的是是形如 $a + bi \ (a,b\in \mathbb{Z})$ 的复数。**高斯质数**指的是所有不能被写成两个非 $\pm 1$ 非 $\pm i$ 的高斯整数的乘积的高斯整数。

所以 $K$ 是平方和等价于 $K$ 是两个共轭高斯整数的乘积。

不那么神奇的结论：高斯整数在不关心乘上 $\pm1,\pm i$ 倍的情况下几乎可以唯一分解，也就是分解得到的每个高斯质数列出来一定能找到 $\pm1,\pm i$ 倍对上。

神奇的结论：根据费马平方和定理，对于奇质数，奇质数，奇质数： $$ (\exists x,y.\ p = (x+yi)(x-yi)) \iff p \bmod 4 = 1 $$ 也就是说，$p = 4k+1$ 时有四种方式写成两个共轭高斯整数的乘积： $$ \begin{array}{rcl} p &=& (x+yi)(x-yi)\\ &=& (x-yi)(x+yi) \\ &=& (y+xi)(y-xi) \\ &=& (y-xi)(y+xi) \end{array} $$ $p = 4k+3$ 时不能。

$p=2$ 时有两种： $$ \begin{array}{rcl} p &=& (1+i)(1-i)\\ &=& (1-i)(1+i) \end{array} $$ 所以我们开开心心地对 $K$ 进行了质因数分解。最后得到的应该是 $K=u \hat{u}$（其中 $\hat{x}$ 是共轭复数）。对于每个质因数幂 $p^\alpha$：

• 如果 $p = 2$ 或 $p=4k+1$，那么设 $p=x^2+y^2$，则对 $u$ 贡献 $(x+yi)^\alpha$，对 $\hat{u}$ 贡献 $(x-yi)^\alpha$。
• 如果 $p=4k+3$，那么：
  • 如果 $\alpha = 2m$，则对 $u$ 和 $\hat{u}$ 都贡献 $p^m$
  • 如果 $\alpha = 2m+1$ 就没戏了，return false

然后乘完了之后……

等一下……好像要 $\gcd(A,B)=1$，怎么办。

假设 $gcd(A,B)=c>1$，那么 $u=c \cdot ((A/c) + (B/c)i)$。对 $c$ 进行高斯质因数分解，里面得到的一定是：

• $p = 4k+3$ 质数的 $p^m$，病在骨髓，无奈何也，显然不行。
• $p = 4k+1$ 质数的 $(x+yi)^\alpha$，非常安全。
• $p = 2$ 的 $(1+i)^n$，在 $n=0$ 或 $1$ 时很安全，$n \geq 2$ 就不行了。

后面两个为什么？因为现在我们已经什么可以害怕的让 $p=4k+3$ 的质因数“无奈何也”了，所以 $c$ 分解完一定是一堆共轭虚高斯质数的乘积，也就是 $c$ 的高斯质因子里面，一定有虚高斯质数 $s$ 和其共轭 $\hat{s}$ 同时存在。所以，我们在上面对 $u$ 贡献 $s$ 之后，就不能贡献 $\hat{s},-\hat{s},i\hat{s},-i\hat{s}$。

• 各个正常质数之间的高斯质因子不互相影响。
• 对于 $p = 4k+1$，两个 $x+yi$ 之间没有影响（显然 $x \neq y$）。
• 对于 $p = 2$，很不幸，$s = 1+i$ 的时候 $i \hat{s} = 1+i=s$，而 $\hat{s} = 1-i$，所以 $2$ 的幂大于 $1$ 的时候是没法弄的，所以 $2^\alpha$ 里面只能 $\alpha = 0$ 或者 $\alpha = 1$。

也就是，这样的条件下，最终得到的 $u$ 是一堆 $x+yi$ 乘出来的，如果 $c > 1$，那么不能有 $4k+3$ 质数为约数，如果是别的，那么也可以质因数分解出 $x - yi$ 的因子，但是获得 $u$ 的时候没有它，矛盾。（本段由 hld67890 提供）

综上，$\exists A,B.\ K = A^2+B^2\ (\gcd(A,B)=1)$，当且仅当 $K$ 质因数分解后，没有 $p = 4k+3$ 的质因数，且 $2$ 的幂是 $0$ 或 $1$。

面积 $S$

我们可以拿 $K​$ 当分母，另一个平方数 $C^2​$ 当分子。

既然 $S$ 是有理数，我们也可以给 $S$ 质因数分解。想办法凑出每个 $p^\alpha$：

• $p = 4k+1$，我们可以在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次，也可以在分母上 $\alpha_d\ \mathtt{\text{-=}}\ 1$ 任意次，也就是 $\alpha$ 任意
• $p = 4k+3$，我们只能在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次，不能在分母减，所以 $\alpha \geq 0$ 且 $\alpha \bmod 2 = 0$
• $p = 2$，我们可以在分子上 $\alpha_n\ \mathtt{\text{+=}}\ 2$ 任意次，分母上 $\alpha_d\ \mathtt{\text{-=}}\ 1$ 最多一次，所以 $\alpha \geq -1$

得到平方数分子 $C^2$，就可以得到 $C$；得到分子 $K$，就可以用上一小节里面的方法凑出 $A,B$。然后用 exgcd 求出 8 个点的坐标。

平方和 $A^2 + B^2$ 续

怎么得到可以写成质数的平方和是哪两个数的平方和？打表：

for (i = 1; i * i < maxn; i ++)
    for (j = i; j * j < maxn - i * i; j ++)
        m = i * i + j * j
        A[m] = i
        B[m] = j

为什么不用直接对 $K$ 查表？因为 $K$ 可能会超过 maxn。

算法总结

• 打表打出 $A, B$
• 线性筛，预处理“质因数分解树”
• 对每个查询 $S$
  • 质因数分解 $S$
  • 化为 $S = C^2 / K$ 的形式
  • 如果能求出 $A, B$
    • 求出点的坐标并输出
  • 否则：
    • 输出 impossible

复杂度：$O(M+T\log M)$

这个……这个，好像有点快啊。

感谢

首先感谢国家，为我提供了良好的教育环境和指导，培养了我的学习兴趣。

然后感谢 3blue1brown 的视频 'Pi hiding in prime regularities' 让我得知了平方和和高斯整数相关的知识。

然后感谢最开始提出这个问题的人。真的是很有趣的问题，原题和当时我给的答案在这里。

然后感谢 Geogebra，我用的这个软件画的题里的那个图，真的很漂亮。

然后感谢 Typora，题解是用这个软件写的。

感谢 LibreOJ 和 UOJ 给我提供了这个交流的机会。