我可能有时候用 质数，有时候用 素数，大家懂的都懂即可（
高斯整数是形如$a+bi$的数，其中$a,b$都是整数。
画到复平面上，高斯整数就是整点。
高斯整数对加法和乘法都是封闭的，并且存在加法单位元、逆元和乘法单位元。然而只有$1,-1,i,-i$是可逆元(有乘法逆元)，当然这四个构成一个群，称为高斯整数的可逆元群。
对于$z=a+bi$，定义$\overline{z}=a-bi$。定义范数，或者我更喜欢叫模长$\Vert z\Vert=a^2+b^2$。
容易发现几个性质 : $\overline{u+v}=\overline{u}+\overline{v},\overline{uv}=\overline{u}\overline{v},\Vert u\Vert=u\overline{u},\Vert uv\Vert=\Vert u\Vert\Vert v\Vert$。
高斯素数
高斯整数里也有素数。当然这里的素数还是不能被别的数乘一乘得到的数。
这里先只给出定义，高斯素数的判定定理是基于费马二平方和定理的，这个定理的证明则要用到高斯素数的概念/jy
自然数里面有质因数分解，高斯整数也有高斯素数分解，这是废话。
带余除法，取膜，gcd和exgcd
我们定义$\lfloor\frac{a}{b}\rfloor$就是把$\frac{a}{b}$的实部虚部都四舍五入得到的东西。
为什么这么搞?因为性质确实很好。具体怎么好……你可以认为它有和数论里面带余除法一样好的性质。
1
2
3
4
5
6
7
8
#define round(x) ((int)((x)+0.5))
inline Complex operator / (const Complex &a,const Complex &b)
{
double x=sqr(b.x)+sqr(b.y);
return {round((a.x*b.x+a.y*b.y)/x),round((a.y*b.x-a.x*b.y)/x)};
}
inline Complex operator % (const Complex &a,const Complex &b){ return a-a/b*b; }
Complex gcd(Complex a,Complex b){ return b.x||b.y?gcd(b,a%b):a; }
啊你说exgcd在哪里?它跟普通的exgcd完全一样，所以没什么好说的（实际上是我忘了exgcd咋写了
二平方和分解
高斯整数的重要应用。
费马二平方和定理 一个奇素数$p$可以被分解成两个平方数的和，当且仅当它可以表示成$p=4k+1$，此时一定有恰好一种分解方案。
这里给出一个有趣的证明，它直接地启发我们得到构造二平方和分解的算法。
证明 考虑一定存在一个$w$使得$w^2\equiv -1\pmod{p}$，因为膜$p=4k+1$下，根据欧拉准则$-1$一定是二次剩余。
所以我们知道$p\mid w^2+1=(w+i)(w-i)$。如果$p$是高斯素数，后面两个必然有一个是它的倍数，但是你除一下发现都除不尽，所以$p$不是高斯素数。
于是考虑$p$的高斯素数分解，假设它有一个素因子$u=a+bi$，设$p=uv$。因为$p$不是高斯素数，$v$一定不是可逆元。同时因为$u$是高斯素数，它也一定不是可逆元。
考虑它们的模长，我们有
\[p^2=\Vert p\Vert=\Vert u\Vert\Vert v\Vert=u\overline{u}v\overline{v}\]。由于$\Vert u\Vert$是正整数，它一定是$p^2$的因数之一，而$p^2$只有$1,p,p^2$三个因数。
如果$\Vert u\Vert=1$或$p^2$，都会导出$u$或者$v$是可逆元，所以必有$\Vert u\Vert=p$，于是也有$\Vert v\Vert=p$。
这俩东西模长相同，乘起来是$p$，说明它们只能共轭，也即$v=a-bi$，于是$p=uv=(a+bi)(a-bi)=a^2+b^2$，我们就得到了解。
剩下的问题是证明唯一性，和$4k+3$型素数不能这么分解，此处略去，可以自行百度（
分解$4k+1$型素数
接下来，如何构造$4k+1$型素数的二平方和分解?
那个$w$很好搞，随就行了。接下来问题是怎么找到素因子$u$。
你发现我们不需要找到素因子，只需要找到一个非平凡因子即可，根据分解的唯一性它就是我们要找的素因子。
考虑$\gcd(p,w+i)$，这个东西首先显然是因子。
它一定不是$p$或者$p$乘上可逆元，因为$w+i$不能被$p$除尽，这个刚才证过了。
它一定不是$1$或者$1$乘上可逆元，因为$p\mid(w+i)(w-i)$，如果$\gcd(p,w+i)=1$就说明$p\mid(w-i)$，而$w-i$也不能被$p$除尽，这个刚才也证过了。(可以看出实际上$p$和$1$是对称的。)
于是我们证明了，取$\gcd(p,w+i)$就可以得到上面证明中的一个$u$。
分解任意数，求方案数
接下来，如何构造任意数$n$的二平方和分解，并求方案数?
还是考虑构造$u=a+bi$使得$u\overline{u}=n$。
先把$n$质因数分解。
对于$4k+3$型质因子，它不能分解成$z\overline{z}$的形式，所以我们只能把它分成两半乘到$u$和$\overline{u}$里面去，所以如果这个质因子次数不是偶数则无解(不可能得到共轭)。
对于$4k+1$型质因子，设它的次数是$e$，利用刚才的算法可以把它分解成$z^e\overline{z}^e$，我们可以选择一个$t$，把$z^t\overline{z}^{e-t}$乘到$u$，$z^{e-t}\overline{z}^t$乘到$\overline{u}$，这样可以保证它们共轭，分配到方案数是$e+1$。
对于$2$，可以分解成$(1+i)^e(1-i)^e$，不过你发现不管怎么分配都是本质相同的。
最后还要乘上四个可逆元，方案数变成四倍。
呃，这个方案数的几何意义，是复平面上以原点为圆心，半径$n$的圆上整点个数。
分解可行性和方案数前缀和
容易发现每个质因子是独立的，同时这个可行性和方案数都是积性函数，所以可以用Min_25筛求前缀和。
这个方案数前缀和的几何意义就是圆内整点计数。
高斯素数判定
定理 一个数$u=a+bi$是高斯素数，当且仅当下面两个条件中任意一个成立
-
$a,b$中一个是$0$，另一个是$4k+3$型素数
-
$\Vert u\Vert=a^2+b^2$是(非$4k+3$型)素数
。
证明
首先证明 : 高斯素数$u$的模长$\Vert u\Vert$要么是素数，要么是素数的平方。
考虑把$\Vert u\Vert=u\overline{u}$质因数分解，那么分解中一定存在一个素数$p_i$，使得$u\mid p_i$，否则$u$就不是高斯素数了。
于是我们显然可以得到$\overline{u}\mid \overline{p_i}=p_i$。于是$\Vert u\Vert=u\overline{u}\mid p_i^2$，所以$\Vert u\Vert$一定是素数。
接下来第一个好像很简单。
充分性 : 根据二平方和定理，$4k+3$型素数不能分解成共轭复数的积，而如果不是共轭复数乘上可逆元，积不可能是实数。
必要性 : 不是素数随便分，$2=(1+i)(1-i)$，$4k+1$型素数可以分解成共轭复数的积。
第二个好像也不难。
充分性 : 如果$u=vw$，那么$\Vert u\Vert=\Vert v\Vert\Vert w\Vert$，而$\Vert u\Vert$是质数，所以$v,w$必定一个是可逆元，一个是$u$乘上可逆元，这个分解是平凡的。
必要性 : 上面证过了。
另外，高斯整数的质因数分解难以达到一个较好的复杂度，一般不用（
好像没什么了。又水了一篇blog（