首先要看懂

然后这题已经做完了。

要求半径为\(r\)的圆上的整点数量,就是求半径为\(\sqrt{r^2}\)的圆上的整点数量。

设\(r=\prod_{i=1}^n p_i^{k_i}(p_i\in Prime)\)

则\(r^2=\prod_{i=1}^n p_i^{2k_i}(p_i\in Prime)\)

根据视频内容,我们知道当\(p_i=4n+1(n\in \mathbb{N^+})\)时,答案会乘上\(2k_i+1\);否则不会产生任何贡献(由于\(2k_i\)是偶数,所以即使\(4n+3\)型素数也不会影响答案)。

对\(n\)分解质因数即可。

时间复杂度\(O(\sqrt{n})\)。

code:

#include
    
     using namespace std;int n,m,p[100010],sz,tot,ans=1;int main(){    freopen("1041.in","r",stdin);    freopen("1041.out","w",stdout);    scanf("%lld",&n);    m=sqrt(n);    for(int i=2;i<=m;i++){//小于等于sqrt(n)的线性筛        if(!p[i])p[++sz]=i;        for(int j=1;j<=sz;j++){            if(p[j]*i>m)break;            p[p[j]*i]=1;            if(i%p[j]==0)break;        }    }    for(int i=1,tot=0;i<=sz;tot=0,i++){        while(n%p[i]==0)tot++,n/=p[i];        if((p[i]-1)%4==0)ans*=2*tot+1;    }    if(n!=1&&(n-1)%4==0)ans*=3;//大于sqrt(n)的质因子最多只有一个    printf("%d",4*ans);    return 0;}