题目在此 | 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,题解是用这个软件写的。