补题

[P2508 HAOI2008] 圆上的整点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析：

$y^2=r2-x^2=(r-x)(r+x) $

设$d=gcd(r-x,r+x),r-x=u*d,r+x=v*d$

则原式变为：$y^2=d^2*u*v$

则可以列出两个等式：

$x=\frac{v-u}{2}d,2r=({u+v})d$

枚举2r的约数d并枚举u可以在$o(\sqrt{r}+\sum\frac{2r}{d})$解决该问题，显然时间复杂度不能接受

注意到u,v互质并且等式左边为平方数则u,v为平方数：

不妨设$u=s^2,v=t^2$

则等式变为：$x=\frac{t^2-s^2}{2}d,2r=(s^2+t^2)d$

此时枚举2r的约束d并枚举s可以在$o(\sqrt{r}+\sum \sqrt\frac{2r}{d})$求解

r数的约数可以粗略估计为$2^{10}$最大不会超过r，所以最大时间复杂度为$o(\sqrt{r}*2^{10})$ 约为$3*10^7$

(实际远比这个小)

int ans,R;
void get(int d,int r){
    // cout<<d<<" "<<r<<"\n";
    for(int i=1;i<=r/i;i++){
        int s=i,t=sqrt(r-i*i);
        if(s*s+t*t!=r||__gcd(s,t)!=1)continue;
        int x=(t*t-s*s)/2*d,y=d*s*t;
        // cout<<x<<" "<<y<<"\n";
        if(x>0&&y>0&&x*x+y*y==(R/2)*(R/2))ans+=2;
    }
}
void solve(){
    int r;cin>>r;
    r<<=1;
    R=r;
    for(int i=1;i<=r/i;i++){
        if(r%i==0)get(i,r/i);
        if(r%i==0&&i*i!=r)get(r/i,r/(r/i));
    }
    cout<<(ans+1)*4<<"\n";
}