- 【HAOI2008】圆上的整点 终于完美解决了
高斯整数
Definition 1.1
高斯整数是定义在复数域上的，实部和虚部均为整数的复数集，遵循复数运算法则
形式化的，我们把满足$z=a+bi,其中a,b\in Z$的复数$z$称为高斯整数（Guassian Integers）
Definition 1.2
定义高斯整数$z=a+bi$的$norm$为$N(z)=a^2+b^2$
特别地，定义$norm$等于$1$的高斯整数为$unit$，即单位元
Definition 1.3
对于高斯整数$x,y$，若存在高斯整数$a$使得$ax=y$，则称$x$为$y$的因子，记作$x|y$
Lemma 1.1
对于高斯整数$a,b$，$N(ab)=N(a)N(b)$
证明：设$a=a_1+a_2 i,b=b_1+b_2 i$，则
$LHS=(a_1 b_1 -a_2 b_2)^2+(a_1 b_2+a_2 b_1)^2=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2$
$RHS=(a_1^2+a_2^2)(b_1^2+b_2^2)=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2$
故$LHS=RHS$，引理成立
注：上述证明中，形如$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$的式子称为斐波那契恒等式
根据该恒等式可以得到柯西不等式及其取等条件
Lemma 1.2
对于高斯整数$a,b$，若$a|b$，则$N(a)|N(b)$，且逆命题不成立
证明：
（1）若$a|b$，设$b=az$，则$N(b)=N(az)=N(a)N(z)$，故$N(a)|N(b)$，命题成立
（2）若$N(a)|N(b)$，设$zN(a)=N(b)$，而$z$不一定能表示成$N(z)$的形式，故逆命题不成立
高斯素数
Definition 2.1
若高斯整数$z$不是单位元，且除自身及单位元外没有其他因子，则称$z$为高斯素数（Guassian Prime Integers）
比如说$2=(1+i)(1-i)$，故$2$不是高斯素数，而$3$不能继续分解，是高斯素数
Theorem 2.1
若素数$P$满足丢番图方程$x^2+y^2=P$无解，则$P$为高斯素数
这个定理直接证比较困难，我们证明它的逆否命题：若$P$不是高斯素数，则丢番图方程$x^2+y^2=P$无解
（1）证明必要性：若$P$为素数且$(a,b)$是丢番图方程$x^2+y^2=P$的一组解
则$P=a^2+b^2=(a+bi)(a-bi)$，$P$不是高斯素数
（2）证明充分性：若$P$不是高斯素数，设$P=(x+yi)(a+bi)=ax-by+(bx+ay)i$
由于$P$是整数，故$ax-by=P$且$bx+ay=0$，得到$(a^2+b^2)x=aP$
由于$a+bi$不是单位元，$a^2+b^2\neq 1$，且P为素数，故$a^2+b^2=P$
故$P$不是高斯素数时，上述方程有解
Lemma 2.1
若高斯整数$z$满足$N(z)$是素数，则$z$是高斯素数
我们同样证明它的逆否命题：若$z$不是高斯素数，则$N(z)$不是素数
证明：若$z$不是高斯整数，则存在非单位元$a,b$满足$z=ab$
则$N(z)=N(ab)=N(a)N(b)$，故$N(z)$不是素数
Theorem 2.2
高斯整数的代数基本定理（Fundermental Theorem of Arithmetic for Guassian Integers）若$z$是高斯整数，不考虑单位元的影响，存在唯一的高斯素数分解方式使得$z=\prod z_i^{q_i}$
证明：根据代数基本定理，$N(z)=\prod N(z_i)^{q_i}$是唯一的，故$z=\prod z_i^{q_i}$是唯一的
注：在代数基本定理中$10=2\times5$，若考虑$-1$的话$10=(-2)\times(-5)$，分解不唯一
所以在代数基本定理中不考虑$-1$的影响，类似的，这里也不考虑单位元的影响
Lemma 2.2
$a^2+b^2\equiv 3(mod 4)$恒不成立
证明：（1）若$4|a^2$，则$a^2\equiv 0(mod 4)$
（2）若$4$不是$a^2$的因子，设$a=\prod p_i^{q_i}$，则$a^2=\prod p_i^{2q_i}$
由欧拉定理得$a^2\equiv \prod pi^{2q_i\%\phi(4)}\equiv \prod pi^{2q_i\%2}\equiv 1(mod 4)$
故$a^2 \equiv 0或1(mod 4)$，$a^2+b^2\equiv 0或1或2(mod 4)$
Lemma 2.3
若$q$是素数，且$q\equiv 3(mod 4)$，则$q$为高斯素数
证明：设$q=z_1 z_2$，且$z_1=a+bi$，则
$N(q)=q^2=N(z_1)N(z_2)$，而$N(z_1)=a^2+b^2\not\equiv 3(mod 4)$
故$N(z_1)\neq q$，因此必然有$N(z_1)=1$或$N(z_2)=1$
Lemma 2.4
若$q$为素数，且$q\equiv 1(mod 4)$，则存在高斯素数$z$使得$q=z\overline{z}$
证明：由于$q\equiv 1(mod 4)$，所以$(-1)^{\frac{q-1}{2}}=1$，故$-1$是模$q$意义下的二次剩余
故存在整数$c$满足$c^2\equiv -1(mod q)$，因此$q|(c+i)(c-i)$
但$(c+i)$和$(c-i)$都不能整除$q$，故$q$不是高斯素数，因此存在$z_1,z_2$，使得$q=z_1 z_2$
而$N(q)=q^2=N(z_1)N(z_2)$，故$N(z_1)=N(z_2)=q$，所以$z_1,z_2$互为共轭
平方和问题
Problem 3.1
求丢番图方程$a^2+b^2=n$的整数解$(a,b)$的个数
设$z=a+bi$，则$z\overline{z}=a^2+b^2=n$，所以问题就变成了求乘积为$n$的共轭高斯整数的数目
我们把$n$按照如下方式分解：$n=2^a \prod p_i^{q_i} \prod p_j^{q_j}$，其中$p_i \equiv 1(mod4)$，$p_j \equiv 3(mod 4)$
那么我们只需要把这些因子划分成两部分使得这两部分乘积的$norm$相等，划分的方案数就是答案
由Lemma2.3可知，$p_j$已经是高斯素数，不能继续分解
只能均分到这两部分，显然如果存在$q_j$是偶数，则方程无解
由Lemma2.4可知，$p_i$可以继续分解为两个共轭高斯整数
设$p_i=z\overline{z}$，则$p_i^{q_i}=z^{q_i}\overline{z}^{q_i}$
而复数相乘满足$norm$相乘，辐角相加，故分配时$z$与$\overline{z}$对两边模长的贡献是相同的
所以只需要保证两边分配的$z$和$\overline{z}$的总数相同即可
例如$5^2=(2+i)^2 (2-i)^2$，则分配方案如下：
（1）左边：$(2+i)(2+i)$ 右边：$(2-i)(2-i)$
（2）左边：$(2+i)(2-i)$ 右边：$(2-i)(2+i)$
（3）左边：$(2-i)(2-i)$ 右边：$(2+i)(2+i)$
可以看出，$p_i^{q_i}$项共有$(q_i+1)$种分配方案，所以$\prod p_i^{q_i}$的贡献就是$\prod(q_i+1)$
而在Theorem2.2中，我们提到高斯整数分解时可以通过乘以单位元得到不同的分解方案
例如$5=(2+i)(2-i)=(-2-i)(-2+i)=(-1+2i)(-1-2i)=(1-2i)(1+2i)$
在考虑单位元的情况下，高斯整数就有4种分解方案，所以答案应该是$4\prod(q_i+1)$
最后我们再考虑$2^a$项的问题，注意到$2=(1+i)(1-i)=i(1-i)^2$
所以只能把$(1-i)$均等分配到两边，而$i$作为单位元不影响答案，故$2^a$只有一种分配方案
问题至此完美解决，最终的答案就是$4\prod(p_i+1)$
圆上的整点
- 【bzoj1041】圆上的整点AC通道
求方程$x^2+y^2=R^2$的整数解个数
这里右边是$R^2$，设$R=2^a \prod p_i^{q_i} \prod p_i^{q_i}$，其中$p_i \equiv 1(mod 4)$，$p_j \equiv 3(mod 4)$
则$R^2=2^{2a}\prod p_i^{2q_i}\prod p_j^{2q_j}$，因为$2q_j$为偶数，所以这一项不会导致无解
而$2^{2a}以及\prod p_j^{2q_j}$对答案无影响，所以答案就是$4\prod (2q_i+1)$
具体做法就是分解质因数，找到形如$4k+1$的质因子，计算次数即可，时间复杂度$O(\sqrt n)$