平方分解与圆周率

· · 算法·理论

概要

如果你学过：

那么本文将会教会你：

希望没锅。

若无特殊说明，离散介值定理一章除外，本文所有区间 [l,r] 代表 [l,r]\cap\Z。

本文所有定义使用方括号「」包裹。对于非正式名称，使用斜体。

【前置知识】环论

如果你对证明不感兴趣，可以跳过这一章节。

各种环的定义

定义 1：「环（Ring）」是一个配备了运算「加」（+）和「乘」（\cdot）的集合 R（注意不要与实数集 \mathbb R 混淆），满足：

乘法不一定具有交换律。定义一个数对 (a,b,c,d)，他们之间的乘法定义为 (a,b,c,d)(e,f,g,h):=(ae+bg,af+bh,ce+dg,cf+dh)，则 (0,1,0,0)(0,0,1,0)=(1,0,0,0),(0,0,1,0)(0,1,0,0)=(0,0,0,1)。

定义 2：如果环 I,R 满足 I\subseteq R，则称

定义 3：$R[i]$ 是在不改变加法与乘法运算时最小的包含了 $R$ 中所有元素和元素 $i$ 的环。 例如，$\mathbb R[\sqrt{-1}]=\mathbb C$。 定义 4：「交换环」是额外满足 $\forall x,y\in R:xy=yx$ 的环 $R$。 定义 5：如果 $\exists 1\in R:\forall x\in R:1x=x$，那么 $R$ 被称作「幺环」，$1$ 被称作「幺元」或「乘法单位元」。 偶数环 $(\{x\mid x\equiv0\pmod2\},+,\cdot)$ 没有幺元。 定义 6：「整环」是额外满足 $\forall a,b\in R\setminus{\{0\}}:ab\neq 0$ 的幺交换环 $R$。 并非所有幺交换环都是整环，例如模 $6$ 意义整数环 $(\{0,1,2,3,4,5\},(x+y)\bmod6, xy\bmod 6)$ 中，有 $2\times 3\equiv0\pmod 6$。 定义 7：如果对于幺环 $R$ 和 $x\in R$，满足 $\exists y\in R:xy=1$，则称 $x$ 是一个 $R$ 中的「可逆元（unit）」。 $\mathbb Z$ 只有 $\pm1$ 两个可逆元。 定义 8：在整环 $R$ 中满足 $p\neq 0,\forall p\mid ab:p\mid a\lor p\mid b$ 的元素 $p$ 称作「素元」。 定义 9：在整环 $R$ 中满足 $\exists a,b\text{ not unit}:ab=r$ 的元素 $r$ 是「可约元」，否则是「不可约元」。 不可约不一定就是素元，例如在 $\mathbb Z[\sqrt{-5}]$ 中，$3$ 不可约且 $3\mid(1+\sqrt{-5})(1-\sqrt{-5})=1^2-(\sqrt{-5})^2=6$，所以 $3$ 不是素元。 引理 1（整环上的乘法消去律）：整环 $R$ 满足 $\forall a\neq 0,ab=ac:b=c$。 > 证：$ab-ac=0\Rightarrow a(b-c)=0$，是整环，$a$ 又不是 $0$，只能 $b-c=0\Rightarrow b=c$。 ### 理想 定义 10：对于环 $R$ 和其上的元素 $x$，定义运算 $xR:=\{xr\mid r\in R\},Rx:=\{rx\mid r\in R\}$。 定义 11：如果对于 $R$ 的子环 $I$，有 $\forall x\in R:xI\subseteq I$，则称 $I$ 是 $R$ 的一个「左理想」；如果 $\forall x\in R:Ix\subseteq I$，则是「右理想」；如果 $I$ 既是左理想又是右理想，那么他就是 $R$ 的一个「理想（ideal）」。 引理 2：两个理想的交仍然是理想。 > 证： > > 环的封闭性显然，因为 $x,y\in I,x,y\in J$ 必然有 $xy\in I,xy\in J$，从而 $xy\in I\cap J$，各种运算律也随之满足。至于为什么 $r(I\cap J),(I\cap J)r\subseteq(I\cap J)
\forall x\in I\cap J,r\in R:x\in I,x\in J\\ \Rightarrow rx,xr\in I,J\\ \Rightarrow rx,xr\in I\cap J

定义 12：理想间的运算

I+J:=\{i+j\mid i\in I,j\in J\}\\ IJ:=\left\{\sum_{k=1}^ni_kj_k\mid n\in\N,i_k\in I,j_k\in J\right\}

引理 3：理想的运算结果是理想。

证：对于加法，设

i_1,i_2\in I,j_1,j_2\in J,r\in R\\ a=i_1+j_1,b=i_2+j_2\in I+J

则有

a+b=(i_1+i_2)+(j_1+j_2)\in I+J\\ ra=ri_1+rj_1\in I+J

对于乘法，设

i_k,{i'}_k\in I,j_k,{j'}_k\in J,r\in R\\ a=\sum_{k=1}^ni_kj_k,b=\sum_{k=1}^m{i'}_k{j'}_k

则有

a+b=\sum_{k=1}^ni_kj_k+\sum_{k=1}^m{i'}_k{j'}_k\\ ra=\sum_{k=1}^n(ri_k)j_k\in IJ

定义 13：如果理想 I 和集合 A 满足 A\subseteq I 以及 \forall\text{ ideal }J\supseteq A:I\subseteq J，则 I 称为「A 在 R 中的的生成理想」，记作 (A)。

存在性证明：首先，R 肯定是一个包含 A 的理想。然后，如果理想 I,J\supseteq A 互不包含，那么 I\cap J 一定包含 A 且是理想。

定义 14：如果 A=\{a\}，那么 (A) 就是一个「主理想」，也记作 (a)。 a 被称作 (a) 的「生成元」。

环 \mathbb R[x_1,x_2]（变量有 x_1 和 x_2 的所有多项式组成的环）自身不是主理想。

商环

定义 15：对于元素 a\in R 和理想 I，定义 a+I:=\{a+i\mid i\in I\},R/I:=\{a+I:a\in R\}。

注意 R/I 是一个集合的集，例如令 m_i:=\{x\mid x\equiv i\pmod 6\}，则 \N/6\N 代表 \{m_0,m_1,m_2,m_3,m_4,m_5\}。

引理 4：(a+I)+(b+I)=(a+b)+I,(a+I)(b+I)=(ab)+I。

证：

\begin{aligned} (a+I)+(b+I)=&\{(a+b+i+j)\mid i,j\in I\}\\ =&(a+b)+I\\ (a+I)(b+I)=&\{\sum_{k=1}^ni_kj_k\mid i_k\in a+I,j_k\in b+I\}\\ =&\{\sum_{k=1}^n(a+i_k)(b+j_k)\mid i_k,j_k\in I\}\\ =&\{\sum_{k=1}^nab+ai_k+bj_k+i_kj+k\mid i_k,j_k\in I\}\\ \xlongequal{ai_k,bj_k,i_kj_k\in I}&(ab)I \end{aligned}

本文中最常用的商环是模 p 意义下整数环 \Z/p\Z。用环的语言，a+b\equiv c\pmod p 应该写成 (a+\Z/p\Z)+(b+\Z/p\Z)=c+\Z/p\Z，ab\equiv d\pmod p 应该写成 (a+\Z/p\Z)(b+\Z/p\Z)=d+\Z/p\Z。

整除

定义 16：如果对于交换环 R 和 a,b\in R，满足 \exists x\in R:bx=a，则称 b 是 a 的「因子」，b「整除」a，记作 b\mid a。

定义 17：如果对于交换环 R 上的元素 a,b 和可逆元 u，满足 au=b，那么称 a 和 b「相伴」。

定义 18：如果对于交换环 $R$ 和他的元素 $a,b$，满足： $$ \exists d:d\mid a,d\mid b\\ \forall d'\mid a,d'\mid b:d'\mid d $$ 则称 $d$ 是 $a,b$ 的「最大公因数」，记作 $\gcd(a,b)$。 他可能不存在，但是一定在相伴意义下唯一，因为如果有 $d,d'$ 满足条件，则 $d\mid d'\mid d$。 引理 5：整环上的素元都是不可约元。 > 证：对于素元 $r$，考虑当 $r=ab$ 时证明 $a$ 或 $b$ 可逆。由 $r\mid ab$ 和素元的定义得 $r\mid a\lor r\mid b$，不妨设 $r\mid a$。令 $a=cr$，则 $r=ab=crb\Rightarrow cb=1$，故 $b$ 可逆。 ### Euclid 整环 定义 19：如果对于整环 $R$，存在映射 $N:R\to\N$ 使得 $N(0)=0$ 且 $\forall a,b\in R:\exists q,r\in R:a=bq+r,N(r)<N(b)$，则 $R$ 是一个「Euclid 整环」，映射 $N$ 被叫做 $R$ 的「范数」。 范数不一定唯一，例如在 $\N$ 中可以设 $N(x)=x$ 和 $N(x)=2x$。 引理 6：在 Euclid 整环上可以使用辗转相除法求得 $\gcd(a,b)$，且 $\forall a,b,x,y:\gcd(a,b)\mid ax+by$。 > 证明与整数上的辗转相除法正确性和 Bezout 定理类似。 ### 主理想整环 定义 20：如果对于整环 $R$，他的每个理想 $I$ 都是主理想，那么 $R$ 是一个「主理想整环」。 引理 7：Euclid 整环都是主理想整环。 > 证：取理想 $I$ 上范数最小的非 $0$ 元素 $d$，那么所有 $a\in I$ 满足 $a=qd+r$，由 $N(r)<N(d)$ 得 $r=0$，故 $\forall a\in I:\exists q\in I:a=qd$，故 $a\in(d)\Rightarrow I\subseteq(d)$，根据生成理想的定义得 $I=(d)$。 引理 8：主理想整环中的素元和不可约元等价。 > 引理 5 已经证了一半了，下证不可约元都是素元。 > > 设不可约元 $p$ 满足 $p\mid ab$，需要证明 $p\mid a\lor p\mid b$。考虑理想： > > $$ > I:=(p,a)=\{pi+aj\mid i,j\in R\} > $$ > > 因为是主理想整环，所以 $\exists d:(d)=I$。由 $p\in I$ 和 $\{xd\mid x\in R\}=(d)$ 得 $d\mid p$，此时要么 $d,p$ 相伴，要么 $d$ 是可逆元。 > > $d,p$ 相伴时，存在可逆元 $u$ 满足 $ud=p$，从而 > > $$ > I=(d)=(ud)=(p)\\ > a\in(p)\\ > p\mid a > $$ > > $d$ 为可逆元的时候， > > $$ > \exists u:ud=1\\ > 1\in I\\ > \exists i,j\in R:pi+aj=1\\ > b=pib+ajb\\ > p\mid ab\Rightarrow p\mid ajb\Rightarrow p\mid(pib+ajb)\Rightarrow p\mid b > $$ > > 证毕。 ### 唯一分解整环 定义 21：如果 $R$ 中的非零不可逆元 $r$ 都能写成 $\prod_{i=1}^np_i$，其中 $p_i$ 是不可约不可逆元，且 $\{p_n\}$ 在重排和相伴意义下唯一，则称 $R$ 是「唯一分解整环」。 引理 9：唯一分解整环中不可约元和素元等价。 > 证：对于不可约元 $r$ 和 $r\mid ab$，将 $ab$ 进行分解，$r$ 必和其中一个因子相伴，不妨设他可能来自于 $a$（即他一定是 $a$ 的因子，可能是 $b$ 的因子），则 $r\mid a$，故 $r$ 是素元。 引理 10：主理想整环都是唯一分解整环。 > 证： > > $r$ 的分解存在性： > > > 如果 $r$ 是不可约元，那么不必继续分解；否则对满足 $r=r_1r_2$ 的非可逆元 $r_1,r_2$ 继续分解。如果分解不停止，无限进行，那么存在一个序列 $\{r_\infty\}$ 满足 $r_0=r,r_{i+1}\mid r$，且序列中相邻的数两两不相伴。考虑他们生成的理想 $I_i:=(r_i)$，则 $I_i\subset I_{i+1},I_i\subseteq R$。令 $I:=\bigcup_{i=0}^\infty I_i$，则 $I$ 是理想（$\forall a,b\in I:\exists n\in\N:a,b\in I_n$），从而 $I$ 是主理想。令其生成元为 $d$，则 $\exists n\in\N:d\in I_n$，从而 $I\subseteq I_n$，矛盾。 > > $r$ 的分解唯一性： > > > 如果 $r$ 有 $\prod_{i=1}^np_i=\prod_{i=1}^mq_i=r$，那么对于不可约元 $p_1$，一定存在 $p_1\mid q_i$，因为 $q_i$ 也是不可约元，所以他俩相伴，从两个序列里踢出去。以此类推，知道其中一个序列为空，另一个如果不为空，则里面的乘积为 $1$，因此都是可逆元，不符合定义；如果为空，就说明 $n=m$，恰恰证明了两个序列在重排和相伴的意义下唯一。 引理 11：唯一分解整环中任两个元素的最大公约数存在。 > 对于可逆元 $u_1,u_2$ 和唯一分解整环上的数 $r_1=u_1\prod_{i=1}^n{p_i}^{\alpha_i},r_2=u_2\prod_{i=1}^n{p_i}^{\beta_i}$，有 $\gcd(r_1,r_2)=\prod_{i=1}^n{p_i}^{\min(\alpha_i,\beta_i)}$ 在相伴意义下唯一且存在。 ## 【前置知识】二次剩余 给 $a,p$，解方程 $x^2\equiv a\pmod p$。 $p=2$ 时过于简单，所以我们默认 $p$ 为奇质数。 定义 1：如果该方程有解，就称 $a$ 是「$p$ 的二次剩余（quadratic residue）」；否则，称 $a$ 是「$p$ 的二次非剩余（quadratic non-residue）」。 定义 2：Legendre 符号（为方便，省略 $i\pmod p$）: $$ \left(\frac ap\right):= \begin{aligned}\begin{cases} 0,\quad&a\equiv0\\ 1,\quad&a\not\equiv0,a\text{ is a quadratic residue}\\ -1,\quad&\text{otherwise}. \end{cases}\end{aligned} $$ 引理 1：$\left(\frac ap\right)\equiv a^{\frac{p-1}2}$。 > 证明： > > - 如果 $a\equiv 0$，那么两边都是 $0$； > - 否则，如果 $a$ 是二次剩余，那么 $a^{\frac{p-1}2}\equiv{\sqrt a}^{p-1}\equiv 1$； > - 否则，令 $r(i):=ai^{-1}$，那么 > > $$ > r(i)\neq i\\ > r^{-1}=r\\ > \begin{aligned} > a^{\frac{p-1}2}\equiv&\prod_{i\in[1,p),i<r(i)}ir(i)\\ > \equiv&(p-1)!\\ > \overset{\text{Wilson's Theorem}}{\equiv}&{-1} > \end{aligned} > $$ 引理 2：$[1,p)$ 内（若无特殊说明，本节内所有数都在 $[1,p)$ 内）恰有 $\frac{p-1}2$ 个二次剩余。 > 证明： > > 试证 $\left\lvert\{(x^2\bmod p)\mid x\}\right\rvert=\frac{p-1}2$。考虑一个更强的结论：$\forall x:\exist!^*y:x^2\equiv y^2$。这相当于 $(x+y)(x-y)\equiv 0$，由于 $x\neq y$，所以 $x+y\equiv 0,y\equiv-x$。 > > \*$\exist!$ 表示恰好存在一个。 接下来，我们需要将环 $\Z/p\Z$ 扩展至 $\Z/p\Z[\sqrt t]$，其中 $t$ 是任意非二次剩余。 定义 3：对所有 $z=x+y\sqrt t\in \Z/p\Z[\sqrt t]$，定义 $\Re(z):=x,\Im(z):=y$。 定理 1：$\forall u,t=u^2-a:\left(\frac tp\right)=-1\Rightarrow(u+\sqrt t)^{p+1}\equiv a$。 > $$ > \begin{aligned} > (u+\sqrt t)^{p+1}=&(u+\sqrt t)\sum_{i=0}^p\binom piu^i\sqrt t^{p-i}\\ > \equiv&(u+\sqrt t)\left(u^p+\sqrt t^p\right)\\ > \equiv&(u+\sqrt t)\left(u+\sqrt t\left(\sqrt t^2\right)^{\frac{p-1}2}\right)\\ > \equiv&(u+\sqrt t)\left(u+\sqrt t\cdot t^{\frac{p-1}2}\right)\\ > \equiv&(u+\sqrt t)(u-\sqrt t)\\ > \equiv&u^2-t\\ > \equiv&a > \end{aligned} > $$ 定理 2：$\forall u,t=u^2-a,\left(\frac tp\right)=-1:\Im\left((u+\sqrt t)^{\frac{p+1}2}\right)\equiv0,\Re\left((u+\sqrt t)^{\frac{p+1}2}\right)^2\equiv a$。 > 证明： > > 如果存在 $A,B$ 满足 $B\not\equiv0,(A+B\sqrt t)^2\equiv a$，那么 $A^2+tB^2+2AB\sqrt t\equiv a$，从而 $2AB\equiv0\Rightarrow A\equiv 0\Rightarrow B^2t\equiv a$。但是 $\left(\frac tp\right)\left(\frac{B^2}p\right)=-1\times1\neq1=\left(\frac ap\right)$，矛盾。故 $\Im\left((u+\sqrt t)^{\frac{p+1}2}\right)\equiv0$ 得证，结合引理 3 可得 $\Re\left((u+\sqrt t)^{\frac{p+1}2}\right)^2\equiv a$。 推论：$\Re\left((u+\sqrt t)^{\frac{p+1}2}\right)$ 是方程 $x^2\equiv a$ 的一个解。 Cipolla ~~～(∠・ω< )⌒★~~ 算法：随机选取 $u$ 直至 $\left(\frac tp\right)=-1$（期望 $2$ 次），利用快速幂求出 $\Re\left((u+\sqrt t)^{\frac{p+1}2}\right)$，从而在 $\Omicron(\log p)$ 的时间内求解二次同余方程 $x^2\equiv a$。 ## 【前置知识】行列式 如果你对证明不感兴趣，可以跳过这一章节。 定义 1：对一个集合 $T$，他的「全排列」指集合 $$ \{\text{sequence }a\mid\forall i\in T:i\in a,\forall i\in a:i\in T, |a|=|T|\} $$ 记作 $\mathrm{Perm}(T)$。「$n$ 阶置换集」$S_n$ 定义为 $\mathrm{Perm}([1,n])$。$S_n$ 中的元素称作「$n$ 阶置换」。一个 $n$ 阶置换 $\sigma^{-1}$ 是 $\sigma$ 的「逆置换」，当且仅当 $\forall i:{\sigma^{-1}}_{\sigma_i}=i$。显然他是唯一存在的。 定义 2：对于一个排列 $\sigma$，定义他的「逆序对数」$\mathrm{inv}(\sigma):=\sum_{i<j}[\sigma_i>\sigma_j]$，定义他的「符号」$\mathrm{sgn}(\sigma):=(-1)^{\mathrm{inv}(\sigma)}$。 引理 1：对于一个排列 $\tau\in\mathrm{Perm}([1,n]\setminus\{j\})$，如果有 $\sigma\in S_n$ 满足 $$ \sigma=[\tau_1,\tau_2,\dots,\tau_{I-1},j,\tau_I,\dots,\tau_{n-1}] $$ 即 $\sigma$ 是 $\tau$ 在第 $I$ 个位置插入 $j$ 所得的 $n$ 阶置换，那么 $\mathrm{inv}(\sigma)-\mathrm{inv}(\tau)\equiv I-j\pmod 2$。 > 原本的，$j$ 在 $j$ 位置，左边有多少个比 $j$ 大，右边就有多少个比 $j$ 小，$j$ 对逆序对奇偶性贡献为 $0$。$j$ 每移动一格，就会对逆序对造成一个 $\pm1$ 的贡献，移动 $\lvert I-j\rvert$ 格，奇偶性改变 $(I-j)\bmod 2$。 引理 2：$\mathrm{inv}(\sigma^{-1})=\mathrm{inv}(\sigma)$。 > 考虑每一对 $(i,j)$，其中 $i<j$。有 ${\sigma^{-1}}_{\sigma_i}=i,{\sigma^{-1}}_{\sigma_j}=j$。如果 $\sigma_i<\sigma_j$，那么 $(\sigma_i,\sigma_j)$ 在 $\sigma^{-1}$ 中不构成逆序对；$\sigma_i>\sigma_j$ 时构成。 定义 3：一个「$n$ 阶方阵」$A$ 是一个 $n$ 行 $n$ 列若干个元素组成的二维数组： $$ A= \begin{bmatrix} a_{1,1}&&a_{1,2}&&\ldots&&a_{1,n}\\ a_{2,1}&&a_{2,2}&&\ldots&&a_{2,n}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{n,1}&&a_{n,2}&&\cdots&&a_{n,n} \end{bmatrix} $$ 定义 4：对于一个 $n$ 阶方阵 $A$，定义他的「转置」： $$ A^T:= \begin{bmatrix} a_{1,1}&&a_{2,1}&&\ldots&&a_{n,1}\\ a_{1,2}&&a_{2,2}&&\ldots&&a_{n,2}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{1,n}&&a_{2,n}&&\cdots&&a_{n,n} \end{bmatrix} $$ 定义 5：对于一个 $n$ 阶方阵 $A$，定义他的「行列式」$\det(A):=\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma_i}$。 时常将 $\det(A)$ 记作： $$ \begin{vmatrix} a_{1,1}&&a_{1,2}&&\ldots&&a_{1,n}\\ a_{2,1}&&a_{2,2}&&\ldots&&a_{2,n}\\ \vdots&&\vdots&&\ddots&&\vdots\\ a_{n,1}&&a_{n,2}&&\cdots&&a_{n,n} \end{vmatrix} $$ 引理 3：$\det(A)=\det(A^T)$。 > $$ > \begin{aligned} > \det(A)=&\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma_i}\\ > =&\sum_{\sigma'\in S_n}\mathrm{sgn}(\sigma')\prod_{i=1}^na_{\sigma',i}\\ > =&\det(A') > \end{aligned} > $$ > > 第二个等于是因为可以考虑 $\sigma$ 和他的逆置换 $\sigma'$ 一一对应。结合引理 2。 定义 6：对于一个 $n$ 阶方阵 $A$，定义它的「余子式」$A_{ij}$ 为 $A$ 删掉第 $i$ 行第 $j$ 列得到的 $n-1$ 阶方阵： $$ A_{ij}:= \begin{bmatrix} a_{1,1}&&\cdots&&a_{1,j-1}&&a_{1,j+1}&&\cdots&&a_{1,n} \\ \vdots&&\ddots&&\vdots&&\vdots&&\ddots&&\vdots \\ a_{i-1,1}&&\cdots&&a_{i-1,j-1}&&a_{i-1,j+1}&&\cdots&&a_{i-1,n} \\ a_{i+1,1}&&\cdots&&a_{i+1,j-1}&&a_{i+1,j+1}&&\cdots&&a_{i+1,n} \\ \vdots&&\ddots&&\vdots&&\vdots&&\ddots&&\vdots \\ a_{n,1}&&\cdots&&a_{n,j-1}&&a_{n,j+1}&&\cdots&&a_{n,n} \end{bmatrix} $$ 引理 4： $$ \forall I:\det(A)=\sum_{j=1}^na_{I,j}\cdot(-1)^{\lvert I-j\rvert}\cdot\det(A_{Ij}) $$ > 证： > > $$ > \begin{aligned} > \det(A)=&\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma_i}\\ > =&\sum_{j=1}^na_{I,j}\sum_{\sigma\in S_n,\sigma_{I}=j}\mathrm{sgn}(\sigma)\prod_{k\in[1,n],k\neq I}a_{k,\sigma_k}\\ > =&\sum_{j=1}^na_{I,j}\sum_{\tau\in\mathrm{Perm}([1,n]\setminus\{I\})}(-1)^{\lvert I-j\rvert}\mathrm{sgn}(\tau)\prod_{k\in[1,n]\setminus\{I\}}a_{k,\sigma_k}\\ > =&\sum_{j=1}^na_{I,j}\cdot(-1)^{\lvert I-j\rvert}\cdot\det(A_{Ij}) > \end{aligned} > $$ 第二行到第三行是因为：将一个 $\sigma$ 一一对应到一个 $\tau$，使得 $\sigma=[\tau_1,\tau_2,\dots,\tau_{I-1},j,\tau_I,\dots,\tau_{n-1}]$，然后就是引理 1。 这一恒等变形称作「$A$ 在第 $I$ 行做 Laplace 展开」。根据引理 3，有在第 $J$ 列做 Laplace 展开： $$ \forall J:\det(A)=\sum_{i=1}^na_{i,J}\cdot(-1)^{\lvert i-J\rvert}\cdot\det(A_{iJ}) $$ ## 【前置知识】连分数 如果你对证明不感兴趣，可以跳过这一章节。 定义 1：一个「连分数」记作 $[a_0;a_1,a_2,\dots,a_n]$，其值为 $$ a_0+\frac1{a_1+\frac1{\ddots\frac1{a_n}}} $$ 定义 2：$x=[a_0;a_1,\dots,a_n]$ 的「第 $k$ 个渐进分数」定义为 $[a_0;a_1,\dots,a_k]$，记作 $x_k=:\frac{p(x)_k}{q(x)_k}$，其中 $\frac{p(x)_k}{q(x)_k}$ 既约。在不引起歧义的情况下会记作 $\frac{p_k}{q_k}$，将 $\frac ab$ 的第 $k$ 个渐进分数记作 ${\frac ab}_k$。 引理 1： $$ p_k=a_kp_{k-1}+p_{k-2}\\ q_k=a_kq_{k-1}+q_{k-2} $$ 递推的起点为 $$ p_{-1}=1,q_{-1}=0\\ p_{-2}=0,q_{-2}=1 $$ > 证：$p_k$ 可以看作关于 $a_0,a_1,\dots,a_k$ 的多项式 $P_k(a_0,\dots,a_k)$，同理 $q_k=:Q_k(a_0,\dots,a_k)$。此时 $Q_k(a_0,\dots,a_k)=P_{k-1}(a_1,\dots,a_k)$。OI Wiki 上只说了个不妨设，没搞明白。 > > > 分析 $Q_k(a_0,\dots,a_k)$： > > > > $$ > > \begin{aligned} > > &[a_0;a_1,\dots,a_k]\\ > > =&a_0+\frac1{[a_1;a_2,\dots,a_k]}\\ > > =&a_0+\frac1{a_1+\frac1{[a_2;a_3,\dots,a_k]}}\\ > > =&a_0+\frac1{a_1+\frac{Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}}\\ > > =&a_0+\frac1{\frac{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}}\\ > > =&a_0+\frac{P_{k-2}(a_2,\dots,a_k)}{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}\\ > > &Q_k(a_0,\dots,a_k)\\ > > =&a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k) > > \end{aligned} > > $$ > > > > 再来分析 $P_{k-1}(a_1,\dots,a_k)$： > > > > $$ > > \begin{aligned} > > &[a_1;a_2,\dots,a_k]\\ > > =&a_1+\frac1{[a_2;a_3,\dots,a_k]}\\ > > =&a_1+\frac{Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}\\ > > =&\frac{a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k)}{P_{k-2}(a_2,\dots,a_k)}\\ > > &P_{k-1}(a_1,\dots,a_k)\\ > > =&a_1P_{k-2}(a_2,\dots,a_k)+Q_{k-2}(a_2,\dots,a_k) > > \end{aligned} > > $$ > > 一方面： > > $$ > x_k=\frac{p_k}{q_k}=\frac{P_k(a_0,\dots,a_k)}{Q_k(a_0,\dots,a_k)} > $$ > > 一方面： > > $$ > \begin{aligned} > x_k=&[a_0;a_1,\dots,a_k]\\ > =&a_0+\frac1{[a_1;a_2,\dots,a_k]}\\ > =&a_0+\frac1{\frac{P_{k-1}(a_1,\dots,a_k)}{Q_{k-1}(a_1,\dots,a_k)}}\\ > =&\frac{a_0P_{k-1}(a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)} > \end{aligned} > $$ > > 所以 > > $$ > \begin{aligned} > \frac{P_k(a_0,\dots,a_k)}{Q_k(a_0,\dots,a_k)}=&\frac{a_0P_{k-1} > (a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)}\\ > P_k(a_0,\dots,a_k)=&a_0P_{k-1}(a_1,\dots,a_k)+Q_{k-1}(a_1,\dots,a_k)\\ > =&a_0P_{k-1}(a_1,\dots,a_k)+P_{k-2}(a_2,\dots,a_k) > \end{aligned} > $$ > > 考虑一个 $k+1$ 阶方阵： > > $$ > M_k(a_0,\dots,a_k):= > \begin{bmatrix} > a_0&&1&&0&&\cdots&&0&&0&&0\\ > -1&&a_1&&1&&\cdots&&0&&0&&0\\ > 0&&-1&&a_2&&\cdots&&0&&0&&0\\ > \vdots&&\vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ > 0&&0&&0&&\cdots&&a_{k-2}&&1&&0\\ > 0&&0&&0&&\cdots&&-1&&a_{k-1}&&1\\ > 0&&0&&0&&\cdots&&0&&-1&&a_k > \end{bmatrix} > $$ > > 行列号为 $1$ 到 $k+1$。下证 $\det(M_k(a_0,\dots,a_k))=P_k(a_0,\dots,a_k)$。 > > > $k=0$ 时，$\det(M_0(a_0))=a_0=P_0(a_0)$。 > > > > $k=1$ 时，$\det(M_1(a_0,a_1))=a_0a_1-1\times(-1)=a_0a_1+1=P_1(a_0,a_1)$。 > > > > $k\ge 2$ 时，考虑对 $M_k(a_0,\dots,a_k)$ 在第 $1$ 行做 Laplace 展开： > > > > $$ > > \begin{aligned} > > &\det(M_k(a_0,\dots,a_k))\\ > > =&\sum_{j=1}^{k+1}(M_k(a_0,\dots,a_k))_{1,j}\cdot(-1)^{j-1}\cdot\det((M_k(a_0,\dots,a_k))_{1j})\\ > > =&a_0\det((M_k(a_0,\dots,a_k))_{11})-\det((M_k(a_0,\dots,a_k))_{12}) > > \end{aligned} > > $$ > > > > 对两个加数分别分析。 > > > > 前者： > > > > $$ > > (M_k(a_0,\dots,a_k))_{11}= > > \begin{bmatrix} > > a_1&&1&&\cdots&&0&&0&&0\\ > > -1&&a_2&&\cdots&&0&&0&&0\\ > > \vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ > > 0&&0&&\cdots&&a_{k-2}&&1&&0\\ > > 0&&0&&\cdots&&-1&&a_{k-1}&&1\\ > > 0&&0&&\cdots&&0&&-1&&a_k > > \end{bmatrix}\\ > > (M_k(a_0,\dots,a_k))_{11}=M_{k-1}(a_1,\dots,a_k)\\ > > $$ > > > > 后者： > > > > $$ > > (M_k(a_0,\dots,a_k))_{12}= > > \begin{bmatrix} > > -1&&1&&\cdots&&0&&0&&0\\ > > 0&&a_2&&\cdots&&0&&0&&0\\ > > \vdots&&\vdots&&\ddots&&\vdots&&\vdots&&\vdots&&\\ > > 0&&0&&\cdots&&a_{k-2}&&1&&0\\ > > 0&&0&&\cdots&&-1&&a_{k-1}&&1\\ > > 0&&0&&\cdots&&0&&-1&&a_k > > \end{bmatrix} > > $$ > > > > 看到他的第一列只有一个非 $0$，考虑对他在第一列做 Laplace 展开： > > > > $$ > > \begin{aligned} > > &\det((M_k(a_0,\dots,a_k))_{12})\\ > > =&\sum_{i=1}^k((M_k(a_0,\dots,a_k))_{12})_{i,1}\cdot(-1)^{i-1}\cdot\det(((M_k(a_0,\dots,a_k))_{12})_{i1})\\ > > =&-\det(((M_k(a_0,\dots,a_k))_{12})_{11})\\ > > =&-\det(M_{k-2}(a_2,\dots,a_k)) > > \end{aligned} > > $$ > > > > 将分析结果代入，得： > > > > $$ > > \begin{aligned} > > &\det(M_k(a_0,\dots,a_k))\\ > > =&a_0\det((M_k(a_0,\dots,a_k))_{11})-\det((M_k(a_0,\dots,a_k))_{12})\\ > > =&a_0\det(M_{k-1}(a_1,\dots,a_k))+\det(M_{k-2}(a_2,\dots,a_k)) > > \end{aligned} > > $$ > > > > 对比 $\det(M_k(a_0,\dots,a_k))$ 和 $P_k(a_0,\dots,a_k)$，发现他们的初值一样，递推关系一样，所以二者完全相同：$\det(M_k(a_0,\dots,a_k))=P_k(a_0,\dots,a_k)$。 > > 同理，从第 $k+1$ 列展开，得： > > $$ > \det(M_k(a_0,\dots,a_k))=a_k\det(M_{k-1}(a_0,\dots,a_{k-1}))+\det(M_{k-2}(a_0,\dots,a_{k-2}))\\ > P_k(a_0,\dots,a_k)=a_kP_{k-1}(a_0,\dots,a_{k-1})+P_{k-2}(a_0,\dots,a_{k-2}) > $$ > > 回顾 $P$ 的定义，这其实就是： > > $$ > p_k=a_kp_{k-1}+p_{k-2} > $$ > > 对于 $Q$，我们有： > > $$ > P_{k-1}(a_1,\dots,a_k)=a_kP_{k-2}(a_1,\dots,a_{k-1})+P_{k-3}(a_1,\dots,a_{k-2})\\ > Q_k(a_0,\dots,a_k)=a_kQ_{k-1}(a_0,\dots,a_{k-1})+P_{k-2}(a_0,\dots,a_{k-2})\\ > q_k=a_kq_{k-1}+q_{k-2} > $$ > > 递推式证明完毕。将 $p_{-1}=1,q_{-1}=0,p_{-2}=0,q_{-2}=1$ 代入，得： > > $$ > p_0=a_0p_{-1}+p_{-2}=a_0\\ > q_0=a_0q_{-1}+q_{-2}=1\\ > p_1=a_1p_0+p_{-1}=a_0a_1+1\\ > q_1=a_1q_0+q_{-1}=a_0 > $$ > > 符合。证毕。 引理 2：$p_{k+1}q_k-p_kq_{k+1}=(-1)^k$。 > 证： > > $$ > \begin{aligned} > \begin{vmatrix}p_{k+1}&p_k\\q_{k+1}&q_k\end{vmatrix}=&\begin{vmatrix}a_kp_k+p_{k-1}&p_k\\a_kq_k+q_{k-1}&q_k\end{vmatrix}\\ > =&\begin{vmatrix}p_{k-1}&p_k\\q_{k-1}&q_k\end{vmatrix}\\ > =&-\begin{vmatrix}p_k&p_{k-1}\\q_k&q_{k-1}\end{vmatrix}\\ > =&(-1)^{k+2}\begin{vmatrix}p_{-1}&p_{-2}\\q_{-1}&q_{-2}\end{vmatrix}\\ > =&(-1)^k > \end{aligned} > $$ 推论 1：$x_{k+1}-x_k=\frac{(-1)^k}{q_kq_{k+1}}$。 注意，引理 1，引理 2 和推论 1 在 $a_i\notin\Z$ 时同样成立。 定义 3：对 $x=[a_0;a_1,\dots,a_n]$，定义它的「第 $k$ 个余项」$r(x)_k:=[a_k;a_{k+1},\dots,a_n]$。不引起歧义的情况下可能记作 $r_k$。 引理 3：$x-x_k=\frac{(-1)^k}{q_k(r_{k+1}q_k+q_{k-1})}$。 > 证：结合 $x=[a_0;a_1,\dots,a_k,r_{k+1}]$，引理 2 和引理 1。 引理 4：$\lvert x-x_k\rvert\le\frac1{q_kq_{k+1}}$。 > 证：$a_{k+1}=\lfloor r_{k+1}\rfloor\le r_{k+1}$，由引理 1 $q_{k+1}=a_{k+1}q_k+q_{k-1}$ 和引理 3 推得原命题。 ## 【前置知识】其他 ### Dirichlet 卷积 定义 1：$\N\to\Complex$ 的映射叫做「数论函数」。 定义 2：对于两个数论函数 $f,g$，定义 $(f\ast g)(x):=\sum_{ij=x}f(i)g(j)$。函数 $(f\ast g)$ 称作 $f$ 与 $g$ 的「Dirichlet 卷积」。 定义 3：如果数论函数 $f$ 满足 $\forall a,b:f(ab)=f(a)f(b)$，那么 $f$ 是一个「完全积性函数」。 ### 离散介值定理（？） 本章无特殊说明所有区间在 $\R$ 上不在 $\Z$ 上。 这个不是《离散介值定理及其应用》中提到的离散介值定理，但类似。 定理 1：对于定义在 $[l,r]\cap\Z$ 上的函数 $f$，如果 $f(x)=A,f(y)=B,A<B$，那么 $\forall C\in[A,B]:\exists z\in[x,y]:C\in[f(z),f(z+1))$。 > 证：$C=A$ 或 $C=B$ 时显然成立。否则，考虑集合 $S:=\{i\mid f(i)>C\}$，显然 $y\in S$，故 $S$ 非空。考虑 $p:=\min S$，显然 $p>x$，所以 $f(p-1)\le C$。那么 $z:=p-1$ 代入原命题显然成立。 ## Fermat 平方和定理 Fermat 平方和定理：$\forall\text{ odd prime }p:(\exists a,b\in\N:a^2+b^2=p)\Leftrightarrow p\equiv1\pmod4$。 > 证明： > > 定义 $S:=\{(x,y,z)\mid x^2+4yz=p,(x,y,z)\in\N^3\}$，显然是有限的，且里面没有 $0$（$y=0\lor z=0\Rightarrow x^2=p,x=0\Rightarrow 4yz=p$），还一定有 $x\neq y-z$（$x=y-z\Rightarrow (y+z)^2=p$）和 $x\neq 2y$（$x=2y\Rightarrow 4y(y+z)=p$）。 > > 考虑两个映射： > > $$ > f(x,y,z)=(x,z,y)\\ > g(x,y,z)= > \begin{aligned}\begin{cases} > (x+2z,z,y-x-z),\quad&x<y-z\\ > (2y-x,y,x-y+z),\quad&y-z<x<2y\\ > (x-2y,x-y+z,y),\quad&\text{otherwise.} > \end{cases}\end{aligned} > $$ > > 由于 > > $$ > (x+2z)^2+4z(y-x-z)=x^2+4z^2+4xz-4xz+4yz-4z^2=x^2+4yz\\ > (2y-x)^2+4y(x-y+z)=x^2+4y^2-4xy+4yx-4y^2+4yz=x^2+4yz\\ > (x-2y)^2+4y(x-y+z)=x^2+4yz > $$ > > 所以 $f,g:S\to S$。 > > 注意到 $g$ 是对合（自身是自身逆映射的映射）： > > | 第一次所选分支 | 一次映射结果 | 第二次所选分支 | 二次映射结果 | > |:----------:|:----------------:|:--------------:|:--------------------------:| > | $x<y-z$ | $(x+2z,z,y-x-z)$ | $2y'<x'$ | $(x+2z-2z,x+2z-z+y-x-z,z)$ | > | $y-z<x<2y$ | $(2y-x,y,x-y+z)$ | $y'-z'<x'<2y'$ | $(2y-2y+x,y,2y-x-y+x-y+z)$ | > | $2y<x$ | $(x-2y,x-y+z,y)$ | $x'<y'-z'$ | $(x-2y+2y,y,x-y+z-x+2y-y)$ | > > 再来考虑 $g$ 的不动点，$(x,y,z)$ 只有可能走 $y-z<x<2y$ 的分支（否则可以考虑映射后的 $x$，显然 $x+2z,x-2y\neq x$），因而 $2y-x=x$，推出 $x=y$，结合 $x^2+4yz=p$ 得到 $x(x+4z)=p$，所以 $x=1,y=1,z=\left\lfloor\frac{p-1}4\right\rfloor$。他是 $g$ 唯一的不动点。又因为 $g$ 是对合，可以将 $S\setminus{\left\{\left(1,1,\left\lfloor\frac{p-1}4\right\rfloor\right)\right\}}$ 中的元素两两配对，所以 $|S|$ 为奇。又 $f$ 是对合，所以至少存在一个不动点，此时 $y=z$，即 $x^2+y^2=p$，Fermat 平方和定理得证。 考虑两对合， 可得 $f$ 有不动点， 原命题得证。 最天才！ ## 复数与 Gauss 整数 定义 1：对复数 $z=a+bi$ 定义 $\Re(z)=a,\Im(z)=b$。 引理 1：$\forall a_1+b_1i,a_2+b_2i\in\Complex:\frac{a_1+b_1i}{a_2+b_2i}=\frac{a_1b_1+a_2b_2}{{a_2}^2+{b_2}^2}+\frac{a_2b_1-a_1b_2}{{a_2}^2+{b_2}^2}\cdot i$。 > 证： > > $$ > \begin{aligned} > \frac{a_1+b_1i}{a_2+b_2i}=&\frac{(a_1+b_1i)(a_2-b_2i)}{(a_2+b_2i)(a_2-b_2i)}\\ > =&\frac{a_1b_1+a_2b_2+a_2b_1i-a_1b_2i}{{a_2}^2+{b_2}^2}\\ > =&\frac{a_1b_1+a_2b_2}{{a_2}^2+{b_2}^2}+\frac{a_2b_1-a_1b_2}{{a_2}^2+{b_2}^2}\cdot i > \end{aligned} > $$ 定义 2：「高斯整数」是 $\Z[i:=\sqrt{-1}]$ 的元素，即满足 $\Re(z),\Im(z)\in\Z$ 的复数 $z$。 定义 3：高斯整数 $z=a+bi$ 的共轭是 $\overline z=a-bi$。 定义 4：高斯整数的「范数」为 $N(z):=\Re^2(z)+\Im^2(z)$。 引理 2：$\forall z_1,z_2\in\Z[i]:N(z_1)N(z_2)=N(z_1z_2)$。 > 显然。 引理：$\forall a,b\neq 0\in\Z[i]:\exists q,r\in\Z[i]:a=bq+r,N(r)\le\frac12N(b)<N(b)$。 > 证： > > 令 > > $$ > \left(\frac ab\right)_\Complex=:x+yi\\ > x':=\left\lfloor x+\frac12\right\rfloor\\ > y':=\left\lfloor y+\frac12\right\rfloor\\ > q:=x'+y'i > $$ > > 则 > > $$ > |x-x'|,|y-y'|\le\frac12\\ > r=a-bq=b(x+yi-q)=b(x-x'+(y-y')i) > $$ > > 考虑其范数： > > $$ > N(r)=N(b)((x-x')^2+(y-y')^2)\le\frac12N(b)<N(b) > $$ 注意在 $2x\in\Z$ 或 $2y\in\Z$ 时，取 $x'=\lfloor x\rfloor$ 或 $y'=\lfloor y\rfloor$ 也是合法的，因此 $(q,r)$ 不一定唯一。但是我们只要求存在。 推论：$\Z[i]$ 是 Euclid 整环，素元与不可约元等价，具有唯一分解性，最大公因数一定存在。 前面讲了 6kb 的环论就是为了这一句话。 ## 平方分解 定义：对于 $a\in\N$，如果 $\exists x,y\in\Z:x^2+y^2=a$，则称 $a$ 是「平方分解数」。 引理：一个数是平方分解数当且仅当他能被表示成一对共轭高斯整数的积。 > 证：$x^2+y^2=a\Leftrightarrow(x-yi)(x+yi)=a$。 ### 分解模 $4$ 余 $1$ 质数 令 $p=:4n+1$，本小节的 $p$ 默认全部模 $4$ 余 $1$，全部字母代表整数。 引理：$\forall p:\exists!^*0<a<b:a^2+b^2=p$。 \*$\exists!$ 表示「唯一存在」。 > 证： > > 考虑其等价命题：如果 $\exists x,y,u,v\in\N^+,(x,y)\neq(u,v),(x,y)\neq(v,u):x^2+y^2=u^2+v^2=p$，则 $p$ 是合数。 > > $(x,y),(u,v)$ 两个数对，每个数对都恰有一奇一偶，不妨设 $x,u$ 偶，$y,v$ 奇，$x<u$。由于 $2\mid\gcd(u-x,y-v)$ 且他们都大于 $0$，可以设正整数 > > $$ > d:=\frac{\gcd(u-x,y-v)}2\\ > a:=\frac{u-x}{2d}\\ > b:=\frac{y-v}{2d} > $$ > > 则 $a\perp b$。那么 > > $$ > x^2+y^2=u^2+v^2\\ > u^2-x^2=y^2-v^2\\ > (u-x)(u+x)=(y-v)(y+v)\\ > 2ad(2ad+2x)=2bd(2bd+2v)\\ > a^2d+ax=b^2d+bv > $$ > > 等号所代表的数同时被 $a,b$ 整除，且 $a\perp b$，所以可以设正整数 > > $$ > c:=\frac{a^2d+ax}{ab} > $$ > > 从而 > > $$ > a^2d+ax=abc\\ > x=\frac{abc-a^2d}a=bc-ad\\ > y=2bd+v=ac+bd\\ > p=x^2+y^2=(bc-ad)^2+(ac+bd)^2=(a^2+b^2)(c^2+d^2) > $$ > > 由 $a,b,c,d\in\N^+$ 推得 $p$ 为合数。 下面让我们来构造一组 $x,y$ 使得 $x^2+y^2=p$。 1. 找到 $c$ 使得 $c^2\equiv -1\pmod p, c<\frac p2$（由于 $\left(\frac{-1}{4k+1}\right)\equiv(-1)^{\frac{(4k+1)-1}2}=1$，所以 $a$ 一定存在）； 2. 找到一个 $\frac ab$，满足 $\exists k:\frac ab={\frac cp}_{k},\frac{a'}{b'}={\frac cp}_{k+1},b\le\sqrt p, b'>\sqrt p$（这一步可以用连分数渐进分数的递推式），此时 $(bc-pa)^2+b^2=p$。 > 正确性证明： > > 存在性是容易的：最后一个 $b$ 一定是 $p$，$a$ 一开始是 $0$，由离散介值定理部分的定理 1 知存在性。 > > 根据连分数引理 4， > > $$ > \exists\epsilon\le1:\frac cp=\frac ab+\frac\epsilon{bb'}\\ > bc-pa=\frac{\epsilon p}{b'}<\epsilon\sqrt p\\ > b^2<p\\ > (bc-pa)^2+b^2<2p^2\\ > (bc-pa)^2+b^2\equiv b^2c^2+b^2\equiv-b^2+b^2\equiv0\pmod p\\ > p\mid(bc-pa)^2+b^2\\ > (bc-pa)^2+b^2=p > $$ ### 一般整数分解与计数 设我们要分解的整数 $n=(a+bi)(a-bi)$ 可以在 $\N$ 内质因数分解成 $\prod_{i=1}^{k_1}{p_i}^{\alpha_i}\cdot\prod_{i=1}^{k_2}{q_i}^{\beta_i}\cdot2^\delta$，其中 $p_i\equiv1\pmod4,q_i\equiv3\pmod4$。 - 对于每个 ${p_i}^{\alpha_i}$，他在 $\Z[i]$ 中能被分解成相伴意义下唯一的 $(z_i\overline{z_i})^{\alpha_i}$。这 $\alpha_i$ 个 $z_i$ 可以分配给左边 $j\in[0,\alpha_i]$ 个，相应地给右边 $\alpha_i-j$ 个，$\overline{z_i}$ 给左边 $\alpha_i-j$ 个，给右边 $j$ 个，他为方案数贡献 $\alpha_i+1$。注意这里交换重复不算重复。 - 对于每个 ${q_i}^{\beta_i}$，由 Fermat 平方和定理得他在 $\Z[i]$ 中不可分解，我们还要保证 $n$ 分解成一对共轭 Gauss 整数，由 Gauss 整数的唯一分解性得只能是左边右边各 $\frac{\beta_i}2$ 个 $q_i$。当 $\beta_i$ 为偶数时，他对方案数的贡献为 $1$，否则为 $0$。 - 对于 $\delta$ 个 $2=(1+i)(1-i)$，由于 $1+i=i(1-i)$，因此 $2$ 的所有分法在相伴意义下重复，为答案贡献 $1$。 总方案数还要乘上 $\Z[i]$ 的 $4$ 个可逆元，就是 $4\prod_{i=1}^{k_1}(\alpha_i+1)\prod_{i=1}^{k_2}[\beta_i\equiv0\pmod2]$。构造一组也不难，$p_i$ 和 $2$ 随便分 $q_i$ 平均分就行。构造全部也不难，把所有分法枚举一遍即可，复杂度最高 $\Omicron(f(n)+\mathrm{ans}\log n)$，其中 $f$ 是分解质因数的复杂度。这个 $\mathrm{ans}$ 的量级我只会压到每当 $n$ 放大 $5$ 倍时对答案的乘数贡献一个不到 $2$，所以 $\mathrm{ans}\le2^{\log_5n}=n^{\log_25}\approx n^{0.4307}$。 关于那个 $f$，使用 Pollard-Rho 时 $f(n)=\Omicron(n^{\frac14}\log n)$。然而在无穷的意义下有个复杂度更优的算法：[General Number Field Sieve，广义数域筛](https://en.wikipedia.org/wiki/General_number_field_sieve)，其复杂度为 $\Omicron\left(\exp\left(\left(\frac{64}9\right)^{\frac13}(\ln n)^{\frac13}(\ln\ln n)^{\frac23}\right)\right)$。由于这玩意大概在 $n\ge\exp(61.5)\approx5.63\times10^{28}$ 时才快于 Pollard-Rho，所以没有引进 OI 中，用处不大，也不像环论那样对关键定理证明产生影响，所以这里不作细讲。 ## 圆周率 ### $\chi

定义一个函数：

\chi(x):= \begin{aligned}\begin{cases} 1,\quad&x\equiv1\pmod4\\ 0,\quad&x\equiv0\pmod2\\ -1,\quad&\text{otherwise.} \end{cases}\end{aligned}

显然他是完全积性函数。

引理 1：相伴意义下不重复的唯一分解数 \mathrm{ans} 即为 4\cdot(1\ast\chi)，其中 1 是函数值永远为 1 的函数。

令

x=:\prod_{i=1}^k{r_i}^{\theta_i}

其中 r_i 是互不相同的质数，那么小学奥数知识告诉我们：

(1\ast\chi)(x)=\prod_{i=1}^k\sum_{j=0}^{\theta_i}\chi({r_i}^j)
  • 对于 r_i\equiv1\pmod4 的项，他对 \mathrm{ans}(x) 的贡献为 \theta_i+1，而 \sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i}) 正好为 \theta_i+1；
  • 对于 r_i\equiv3\pmod4 的项，当 \theta_i 为偶数时他对答案贡献 1，否则贡献 0，刚好与 \sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i})=1-1+1-1\dots 相等；
  • 对于 r_i=2，他对答案贡献 1，与 \sum_{j=0}^{\theta_i}\chi({r_i}^{\theta_i})=1+0+0+\dots 相等。

最后 \mathrm{ans} 要乘上 4，所以 \mathrm{ans}=4\cdot(1\ast\chi)。

\pi

半径为 R 的圆内整点个数为 \pi R^2+\Omicron(R)\sim\pi R^2，其面积 \pi R^2 在 R\to+\infty 时趋近于圆内整点个数。而 R 半径的圆内整点个数就是对于每个 i\in[1,R^2]，半径为 i 的圆上整点个数之和。而圆上整点个数就是刚刚讲到的 \mathrm{ans}(i)=4(1\ast\chi)(i)。所以：

\begin{aligned} \pi R^2\sim&\sum_{i=1}^{R^2}\mathrm{ans}(i)\\ \frac\pi4\sim&\frac1{R^2}\sum_{i=1}^{R^2}\frac14\mathrm{ans}(i)\\ =&\frac1{R^2}\sum_{i=1}^{R^2}\sum_{d\mid i}\chi(d)\\ =&\frac1{R^2}\sum_{d=1}^{R^2}\left\lfloor\frac{R^2}d\right\rfloor\chi(d)\\ \sim&\sum_{d=1}^{R^2}\frac{\chi(d)}{d}\\ =&\frac11+\frac02-\frac13+\frac04+\frac15+\frac06-\frac17+\dots\\ =&\frac11-\frac13+\frac15-\frac17\ldots \end{aligned}

参考，致谢，以及写在后面

参考与致谢：

这篇文章创建于 2025.02.19，初版完成于 2025.03.28。当时省选模拟出了这么个题：给个整数，构造他的一个平方分解。题解里面只有一堆结论，一个证明没有，但是提到了 P2508 [HAOI2008] 圆上的整点。翻题解翻出来了那个视频，他讲了很多结论，包括高斯整数，\pi 的那个渐进公式，但例如 Gauss 整数的唯一分解性还是感性理解。于是我就去搜资料，搜出来了环论，Fermat 平方和定理等等，但就是没有 4k+1 平方分解唯一性及其构造，这篇文章也就扔掉了。一模和 MOer 一起复习（我们学校四科竞赛都在初中部且教室连在一起，但是 OI 由于没有机房所以教室和午休都在高中部，考试午休的时候 OIer 只能四处游荡）的时候听他们聊起二次剩余于是就提出了 4k+1 分解唯一性的问题，他把那本书给了我。抱着“要不顺便把构造分解也解决了？”的想法，搜到了 Note de M. Hermite 这一页纸，然后是连分数，行列式，最后把这篇文章写完了。

本人第一次写这么大的文章，也是第一次正经投全站推荐上一次投的休闲娱乐，文章肯定有问题，排版，语言，逻辑等等。还请各位大佬多多指教。