高斯素数

· · 算法·理论

高斯素数体系可以用于解出方程 x^2+y^2=z ,其中 x,y,z 为整数.

引入复平面,该方程可化为 (x+yi)(x-yi)=z ,相当于把 z 进行分解.而其中 x+yi 和 x-yi 可能可以继续分解.

一个形如 x+yi 的数,叫做高斯整数,其中 x,y 都是整数.而以上面的分解方式无法继续分解下去的高斯整数,是高斯素数.

一个对应的 x+yi 和 x-yi 叫一对复共轭.一对复共轭同时乘 1 ,同时乘 -1 ,分别乘 i 和 -i ,分别乘 -i 和 i ,都能得到一对新的复共轭,这对应着复平面上的 90 度旋转.因此我们规定其符号后将最终答案乘 4 .而注意到 i+1 和 -i-1 这对复共轭很特殊,它们旋转后有重复.所以对于它们所组成的数 2 ,我们单独考虑.

显然,一个高斯素数如果是整数,它一定是一个质数.手推一下可以发现,\equiv3(mod\ 4) 的素数无法分解,而 \equiv1(mod\ 4) 的素数都可以继续分解.而质数 2 由于上一段所言,并不会影响答案.

由此我们可以构造一个巧妙的函数:设 χ(x)=\Biggr\{ \begin{matrix}1,x\equiv1(mod\ 4)\\-1,x\equiv 3(mod\ 4)\\0,else\end{matrix}

而对于一个数 x 的最终分解个数 ans=4f(x)=\prod (χ(p)+χ(p^2)+...+χ(p^k))

对于 p\equiv1(mod\ 4),它对应了每多一个质因数 p,贡献的复共轭就会多 1.

对于 p\equiv3(mod\ 4),它对应了如果 k 是偶数,我们就能将其均匀分配至乘号两端;否则无解.

对于 p=2 ,它对应了其数量不影响解.

拆开式子,得 f(x)=\sum\limits_{d|x}χ(d) ,而这显然是一个积性函数.我们可以线性筛求解.