补题

P2508 [HAOI2008] 圆上的整点 - 洛谷

分析

圆上的整点满足：

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

设

$$d=\gcd(r-x,r+x), \quad r-x=ud, \quad r+x=vd$$

则原式变为：

$$y^2=d^2uv$$

同时可以得到：

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

如果直接枚举 $2r$ 的约数 $d$，再枚举 $u$，复杂度仍然不能接受。

注意到 $u$、$v$ 互质，并且等式左边为平方数，所以 $u$、$v$ 都应为平方数。不妨设：

$$u=s^2, \quad v=t^2$$

则有：

$$x=\frac{t^2-s^2}{2}d, \quad 2r=(s^2+t^2)d$$

此时枚举 $2r$ 的约数 $d$，再枚举 $s$ 即可。约数数量较小，整体复杂度约为：

$$O(\sqrt r \cdot 2^{10})$$

实际复杂度会比这个上界更小，可以通过。

代码

int ans,R;
void get(int d,int r){
    // cout0&&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";
}