不定方程

勾股定理的通解（构造解）需满足：gcd(u,v)==1,d,u,v都是正整数,且当d==1时，(x,y,r)是一组本源勾股数

sol:O(srqt(2r))枚举d|2r,判断2*r/d 和 d是否==u^2+v^2(gcd(u,v)==1,u,v为正整数)，O(sqrt(2r/d))枚举u就好

#define int long long
int r,ans;

inline bool check(int u,int V){
    int v=(int)(sqrt(V));
    if(V==v*v)
        return __gcd(u,v)==1;
    return 0;
}

inline int calc(int sum){
    int res=0;
    for(int u=1;u*u<sum/2;++u)
        res+=check(u,sum-u*u);
    return res;
}

#undef int
int main(){
#define int long long
    #ifdef WIN32
    freopen("","r",stdin);
    #endif
    rd(r);
    for(int d=1;d*d<=2*r;++d){
        if(2*r%d==0)
            ans+=calc(2*r/d)+(d*d==2*r?0:calc(d)); 
    }
    printf("%lld\n",ans*4+4);
    return 0;
}

P2508 [HAOI2008]圆上的整点

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11644478.html