前置知识

1.基础的复数知识

2.基础的数论定理

3.一点点离散数学

4.一点点抽象代数（如果你只学算法，那么不用知道；如果想了解原理，可以去维基百科）

观前提醒

本文含有大量数论知识和证明，萌新完全阅读需要至少1小时。全文的证明都加了引用，对证明不感兴趣的读者可以选择性跳过。

二次剩余

对于正整数 n，奇质数p\nmid n，如果存在正整数 x 使 x^2\equiv n\pmod{p}，则 n 为模 p 的二次剩余。

以下的a\equiv b均指a\equiv b\pmod{p}。

定义勒让德符号(\frac{n}{p})=\begin{cases} 1 & n是p的二次剩余\\ -1 & n不是p的二次剩余\\ 0 & p|n \end{cases}

定理1：(\frac{n}{p})\equiv n^{\frac{p-1}{2}}。

证明：

1.若n是模p的二次剩余，则根据费马小定理，n^{\frac{p-1}{2}}=(\sqrt n)^{p-1}\equiv1

2.若n不是模p的二次剩余，则根据扩展欧几里得算法，对于i\in[1,p-1]都有唯一的j\in[1,p-1],i\neq j满足ij\equiv n。这样的数对一共有\frac{p-1}{2}个，因此n^{\frac{p-1}{2}}\equiv (p-1)!。根据威尔逊定理，(p-1)!\equiv-1，那么n^{\frac{p-1}{2}}\equiv-1。

3.若p|n，显然有p|n^{\frac{p-1}{2}},n^{\frac{p-1}{2}}\equiv0。

定理2：[1,p-1]中有\frac{p-1}{2}个二次剩余。

证明：设x,y\in[1,p-1],x\neq y,x^2\equiv y^2，则(x+y)(x-y)\equiv0。由于0<|x-y|<p，必定是x+y\equiv 0。这样的数对(x,y)共有\frac{p-1}{2}个，因此共有\frac{p-1}{2}个二次剩余。

根据上述证明，发现剩余系中的二次剩余与实数的平方根具有统一性：要么没有；要么有一个平方根(0)；要么有一对平方根，它们互为相反数。

求二次剩余的方法

问题：已知正整数n,p（p为奇质数），求所有数x，使x^2\equiv n。题目链接

在[0,p-1]中随机产生一个数a，令w=a^2-n，若(\frac{w}{p})=-1，(a+\sqrt w)^{\frac{p+1}{2}}是x的一个解。

证明：首先，显然有\binom{p}{x}\equiv 0,x\in[1,p-1]。因此，(a+\sqrt w)^p=\sum_{i=0}^p\binom{p}{i}a^i(\sqrt w)^{p-i}\equiv a^p+(\sqrt w)^p。根据费马小定理，a^p\equiv a。根据定理1，(\sqrt w)^p=\sqrt ww^{\frac{p-1}{2}}\equiv -\sqrt w。因此，(a+\sqrt w)^{p+1}\equiv(a+\sqrt w)(a-\sqrt w)=a^2-w=n

这里就出现了一个问题：w明明是非二次剩余，怎么还会有\sqrt w呢？这里我们需要用到扩域的思想。定义\mathbb{Z}_p[\sqrt w]=\{a+b\sqrt w\mid a,b\in\mathbb{Z}\cap[0,p)\}，根据(a_1+b_1\sqrt w)(a_2+b_2\sqrt w)\%p=(a_1a_2+b_1b_2w)\%p+(a_1b_2+b_1a_2)\%p\sqrt w，在\mathbb{Z}_p[\sqrt w]上定义乘法，可以实现快速幂。

由于[1,p-1]中有一半是二次剩余，因此随机的期望次数为2。这种做法可以求出一个二次剩余的解，另一个解是它的相反数。

代码如下：

inline int ksm(int a,int b)
{
    int c=1;
    while(b){if(b&1)c=1ll*c*a%MOD; a=1ll*a*a%MOD; b>>=1;}
    return c;
}
inline int lrd(int x){return ksm(x,MOD>>1);}//勒让德符号
struct cplx
{
    int x,y;
    inline friend cplx operator *(cplx a,cplx b)
    {
        return {(1ll*a.x*b.x+1ll*a.y*b.y%MOD*w)%MOD,(1ll*a.x*b.y+1ll*a.y*b.x)%MOD};
    }
    inline friend cplx operator ^(cplx a,int b)
    {
        cplx c={1,0};
        while(b){if(b&1)c=c*a; a=a*a; b>>=1;}
        return c;
    }
}a;
void solve()
{
    scanf("%d%d",&n,&MOD); n%=MOD;
    x=lrd(n);
    if(x==MOD-1)printf("Hola!\n");
    else if(!x)printf("0\n");
    else
    {
        x=rand()%(MOD-1)+1; w=(1ll*x*x-n+MOD)%MOD;
        while(lrd(w)<=1)x=rand()%MOD,w=(1ll*x*x-n+MOD)%MOD;
        a={x,1}; a=a^(MOD+1>>1);
        ans1=a.x; ans2=MOD-a.x; if(ans1>ans2)swap(ans1,ans2);
        printf("%d %d\n",ans1,ans2);
    }
}

高斯整数

高斯整数集合\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}，其中i^2=-1

几何意义：复平面上的整点

高斯整数环是欧几里得整环，同样满足裴蜀定理、欧几里得引理、唯一分解定理等基础的数论定理。

高斯整数的可逆元群U(\mathbb{Z}[i])=\{1,i,-1,-i\}。

高斯整数u=a+bi的共轭复数\bar u=a-bi，可逆元的共轭复数是可逆元。

性质：\overline{u+v}=\bar u+\bar v,\overline{uv}=\bar u\bar v,\overline{\frac{u}{v}}=\frac{\bar u}{\bar v}，直接展开即可证明。

高斯整数的范数\|a+bi\|=a^2+b^2，可逆元的范数为1。

性质：\|ab\|=\|a\|\|b\|，直接展开即可证明。

费马平方和定理

定理表述：奇质数能表示为两个平方数之和的充分必要条件是该质数被4除余1。

接下来给出欧拉对这个定理的证明。

将可以表示为两个整数平方和的数定义为平方分解数。

定理1：平方分解数的积是平方分解数。

证明：(a^2+b^2)(p^2+q^2)=(ap+bq)^2+(aq-bp)^2=(ap-bq)^2+(aq+bp)^2

定理2：平方分解数被素平方分解数整除的商是平方分解数。

证明：(ap+bq)(ap-bq)=a^2p^2-b^2q^2=a^2(p^2+q^2)-q^2(a^2+b^2)

由于p^2+q^2|a^2+b^2，因此p^2+q^2|(ap+bq)(ap-bq)。p^2+q^2是质数，则它整除其中一个因子，不妨设p^2+q^2|ap+bq，另一种情况同理。(p^2+q^2)^2|(a^2+b^2)(p^2+q^2)=(ap+bq)^2+(aq-bp)^2，则 有(p^2+q^2)^2|(aq-bp)^2，那么p^2+q^2|aq-bp

因此，\frac{a^2+b^2}{p^2+q^2}=\frac{(a^2+b^2)(p^2+q^2)}{(p^2+q^2)^2}=(\frac{ap+bq}{p^2+q^2})^2+(\frac{aq-bp}{p^2+q^2})^2

定理3：平方分解数被非平方分解数整除的商必有一个非平方分解因子。

证明：设a=x\prod p_i，a是平方分解数，x是非平方分解数。如果p_i均是平方分解数，根据定理2，用p_i一个个去除a，所得结果x也是平方分解数，与假设矛盾。

定理4：如果a和b互素，则a^2+b^2的所有因子都是平方分解数。

这一步的证明运用了无穷递降法。

证明：假设x|a^2+b^2,a=mx+c,b=nx+d(c,d\in[-\frac{x}{2},\frac{x}{2}])

定理5a：形为4n+1的素数是平方分解数。

证明：设p=4n+1。根据费马小定理，\forall x\in[1,4n],p|x^{4n}-1，则p|(x+1)^{4n}-x^{4n}，那么有p|(x+1)^{2n}+x^{2n}或p|(x+1)^{2n}-x^{2n}。假设\exists x,p|(x+1)^{2n}+x^{2n}，根据定理4，p是平方分解数。否则，\forall x\in[1,4n],p|(x+1)^{2n}-x^{2n}=\Delta x^{2n}，根据整除可加减的性质，x^{2n}的任意阶差分都可以被p整除。因此，p|\Delta^{2n} x^{2n}=(2n)!，而p|(2n)!显然不成立。因此这种情况不存在，p必为平方分解数。

定理5a证明了充分性，还需要证明必要性。

定理5b：形为4n+3的数不是平方分解数。

证明：完全平方数模4只可能为0或1，因此不存在两个完全平方数之和模4为3。

至此，我们证明了费马平方和定理：奇质数是平方分解数的充分必要条件是该质数形为4n+1。

高斯素数

高斯整数环的素元称为高斯素数。

1.高斯素数的共轭复数是高斯素数。

证明：设p是高斯素数，\bar p=uv,u,v\not\in U(\mathbb{Z}[i])，则p=\overline{uv}=\bar u\bar v，与p是高斯素数矛盾。

2.a+bi是高斯素数当且仅当下列条件之一成立：

(1)a,b一个为0，另一个的绝对值为4k+3型素数。根据费马平方和定理，显然成立。

(2)a^2+b^2为4k+1型素数或2

证明：设u=a+bi,u\bar u=p。设u=de,1<\|d\|,\|e\|<\|u\|。那么p=u\bar u=de\bar d\bar e=(d\bar d)(e\bar e)，其中d\bar d,e\bar e均为大于1的正整数，与p是质数矛盾。

定义带余除法

>证明：假设$\frac{a}{b}=x+yi,q=x'+y'i$，其中 $x'=\lfloor x+\frac{1}{2}\rfloor,y'=\lfloor y+\frac{1}{2}\rfloor$，则有$|x-x'|\le\frac{1}{2},|y-y'|\le\frac{1}{2}$。 >$r=a-qb=b((x-x')+(y-y')i)

\|(x-x')+(y-y')i\|=(x-x')^2+(y-y')^2\le\frac{1}{2} \|r\|=\|b\|\|(x-x')+(y-y')i\|\le\frac{1}{2}\|b\|

上述证明同时也是求商和余数的算法。

因此，可以对两个高斯整数进行辗转相除法，算出它们的最大公因数。代码如下：

inline cplx operator /(cplx a,cplx b)
{
    double x=b.x*b.x+b.y*b.y;
    return {round((a.x*b.x+a.y*b.y)/x),round((a.y*b.x-a.x*b.y)/x)};
}
inline cplx operator %(cplx a,cplx b){return a-a/b*b;}
inline cplx gcd(cplx a,cplx b)
{
    while(b.x||b.y)a=a%b,swap(a,b);
    return a;
}

分解4n+1型素数

题目链接

设p=4n+1,p=u\bar u。首先注意到k^2\equiv-1\Leftrightarrow p|(k+i)(k-i)，则u=gcd(p,k+i)。由于[1,p-1]中一半的数是二次剩余，随机一个t\in[1,p-1]使t^{\frac{p-1}{2}}\equiv -1，则k=t^{\frac{p-1}{4}}=t^n。随机成功概率为\frac{1}{2}，期望随机次数为2。

构造二平方和

问题：求x^2+y^2=n的所有整数解。

考虑将n分解为共轭复数的积，令u=x+yi，则n=u\bar u

1.将n在\mathbb{R}内质因数分解。

2.对4n+3型质数，若次数为偶数，则在u与\bar u中均分，只有1种分法；若次数为奇数，则不存在方案使u与\bar u共轭，方程无解。

3.将4n+1型质数分解。假设p=v\bar v，则p^k=v^k\bar v^k，为了让u与\bar u共轭，分配方案需要使分配给u与\bar u的v与\bar v次数之和相等，即将v^i\bar v^{k-i}分配给u，剩下的分配给\bar u，共有k+1种分法。

4.将2分解为(1+i)(1-i)。由于\frac{1+i}{1-i}=i，无论分配方案如何，分配给u与\bar u的都是(1+i)^k乘以可逆元，方案本质相同，因此随便怎么分配都一样，只有1种分法。

5.最终还可以将u分别乘以4个可逆元，得到(x,y)(-x,-y)(-y,x)(y,-x)4个解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int z,p[105],a[105],cnt,x,y,ans1,ans2[1000005][2];
struct cplx
{
    ll x,y;
    inline friend cplx operator -(cplx a,cplx b){return {a.x-b.x,a.y-b.y};}
    inline friend cplx operator *(cplx a,cplx b){return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
    inline friend cplx operator /(cplx a,cplx b)
    {
        double x=b.x*b.x+b.y*b.y;
        return {round((a.x*b.x+a.y*b.y)/x),round((a.y*b.x-a.x*b.y)/x)};
    }
    inline friend cplx operator %(cplx a,cplx b){return a-a/b*b;}
    inline friend cplx operator ^(cplx a,int b)
    {
        cplx c={1,0};
        while(b){if(b&1)c=c*a; a=a*a; b>>=1;}
        return c;
    }
}u1[105],u2[105],u;
inline cplx gcd(cplx a,cplx b)
{
    while(b.x||b.y)a=a%b,swap(a,b);
    return a;
}
inline int rand_int(){return rand()<<15^rand();}
inline int ksm(int a,int b,int MOD=1e9)
{
    int c=1;
    while(b){if(b&1)c=1ll*c*a%MOD; a=1ll*a*a%MOD; b>>=1;}
    return c;
}
inline void addans(int x,int y){ans2[++ans1][0]=x; ans2[ans1][1]=y;}
void dfs(int step,cplx s)
{
    if(step>cnt)
    {
        addans(s.x,s.y);
        addans(-s.x,-s.y);
        addans(-s.y,s.x);
        addans(s.y,-s.x);
        return;
    }
    if(p[step]==2||(p[step]&3)==3)dfs(step+1,s*u1[step]);
    else
    {
        cplx x=u2[step]^a[step];
        for(int i=0;i<=a[step];i++)dfs(step+1,s*x),x=x/u2[step]*u1[step];
    }
}
int main()
{
    scanf("%d",&z);
    for(int i=2;i*i<=z;i++)
        if(z%i==0)
        {
            p[++cnt]=i;
            while(z%i==0)z/=i,a[cnt]++;
        }
    if(z>1)p[++cnt]=z,a[cnt]=1;
    for(int i=1;i<=cnt;i++)
        if(p[i]==2)u1[i]=(cplx){1,1}^a[i];
        else if((p[i]&3)==1)
        {
            while(1)
            {
                x=rand_int()%(p[i]-1)+1;
                if(ksm(x,p[i]>>1,p[i])==p[i]-1)break;
            }
            x=ksm(x,p[i]>>2,p[i]); u={p[i],0};
            u1[i]=gcd(u,{x,1});
            u2[i]=u/u1[i];
        }
        else if(a[i]&1){printf("0\n"); return 0;}
        else u1[i]={ksm(p[i],a[i]>>1),0};
    dfs(1,{1,0});
    printf("%d\n",ans1);
    for(int i=1;i<=ans1;i++)printf("%d %d\n",ans2[i][0],ans2[i][1]);
}

求平方分解方案数

令f(n)=\sum_{i=1}^{\lfloor\sqrt n\rfloor}\sum_{j=0}^{\lfloor\sqrt n\rfloor}[i^2+j^2=n]

则方案数为4f(n)。

根据构造二平方和的方法，n中每个素因子的方案可以分开考虑，因此f(n)是积性函数。其中：

1 & p=2\\ k+1 & p=4n+1\\ [k\%2=0] & p=4n+3 \end{cases}

可以使用改动过的min25筛快速求前缀和。具体见题目链接

完结撒花！

参考资料

维基百科

浅谈二次剩余

高斯整数