题意:求半径为 $r$ 的圆上有多少个整点,即求 $x^2+y^2=r^2$ 有多少组整数解。

我们考虑把 $r^2=x^2+y^2$ 变形,得到 $r^2=x^2-(-y^2)=(x+yi)(x-yi)$。

所以我们就需要考虑通过分解 $r^2$ 可以得到多少组不同的 $(x+yi)(x-yi)$。

image-20201110171118981

我们考虑如果有若干对共轭复数分别放在两边,最后得到的也是一对共轭复数,相乘就可以得到整数,我们希望这个整数是 $r$。

那么就考虑如何求并分配这若干对共轭复数。

费马平方和定理:奇素数 p 可以表示为两个正整数的平方和,当且仅当 p 是 4k+1 型的。并且在不考虑两个正整数顺序的情况下,这个表示方法唯一。

引入一个概念:高斯素数,即 3,7 这样形似 4n+3 的素数,他们一定不能被分成 $(x+yi)(x-yi)$ 的形式。

否则,如果是形似 4n+1 的素数,一定能被分成 $(x+yi)(x-yi)$ 的形式。

那么是否还忽略了某个素数呢?没错,2 要特殊考虑,虽然它能被分成 $1^2+1^2=(1+i)(1-i)$,但特殊的是它所分解出的这两个高斯整数的夹角还刚好是 90 度,这个要在计算答案的时候特殊考虑一下。

根据整数的惟一分解定理,我们可以让 $r=p_1^{r_1}*p_2^{r_2}*...*p_k^{r_k}$。考虑每个质因子对答案的影响。

如果这个因子不是高斯素数,也就是它能被分解成 $(x+yi)(x-yi)$,假设它的幂次是 $m$,那么我们可以得到 $m$ 对 $z:(a+bi)$ 和 $\overline z:(a-bi)$,考虑怎么分配。我们可以在左边分配 $[0,m]$ 个$z$,右边分配剩下的 $z$,其他的就填 $\overline z$。这样它对答案的贡献就是 $m+1$。

如果这个因子是高斯因数,也就是它不能被分解成 $(x+yi)(x-yi)$,但是我们又一定要最后得到的等式两边共轭,所以只有当它的幂次 $m$是偶数的时候,才能平均的分配到两边,否则就无解。

当然,我们也可以把 $(x+yi),(x-yi)$ 乘上 $-1,i,-i$ 得到新的分解 $(-x-yi),(-x+yi),(-y+xi),(y+xi),(y-xi),(-y-xi)$,所以我们还要把最后的答案乘上 4。

image-20201110172932198

等等,是不是忘了什么?素数 2 还没有在我们讨论的范围中。它可以分为 $(1+i)(1-i)$,我们还是选择放到两边,但是我们对它分解得到的两个共轭复数来乘上 $-1,i,-i$,得到的分解是 $(-1-i),(-1+i),(-1+i),(1+i),(1-i),(-1-i)$,我们可以发现这样会得到重复的复数。

不妨在几何中理解一下。

上面的乘上 $-1,i,-i$ 其实就是把 $(a+bi),(a-bi)$ 两个点旋转起来,但是当这两个点的夹角是90度的时候,这旋转不能得到新的解,所以2对答案没有影响。

所以最后的答案就是,将 $r^2$ 进行质因数分解,一个高斯素数 $p^m$ 若 $m$ 是奇数,答案为 $0$,否则不会对答案造成影响,一个非高斯素数 $p^m$ 对答案的贡献是 $m+1$,2 忽略不计。

但是由于 $r^2$ 里的每一个质数的指数一定是偶数,所以答案不会为 0。其他的就没有问题了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
int ans(int n){
    int res=1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            int cnt=0;
            while(n%i==0)n/=i,cnt++;
            if(i%4==1)res*=(cnt<<1|1); 
        }
    }
    if(n!=1&&n%4==1)res*=(2+1);
    return res<<2;
}
signed main(){
    int n;
    cin>>n;
    cout<<ans(n)<<endl; 
    return 0;
}
最后修改:2021 年 06 月 23 日
如果觉得我的文章对你有用,请随意赞赏