洛谷2508 [HAOI2008]圆上的整点

题意

一个圆的方程为 $x^2+y^2=r^2$ ，给出 $r$ ，问圆上有多少个点的坐标都是整数。

题解

可以用勾股定理的通解：

$$x=d\dfrac{v^2-u^2}{2} \ , \ y=duv \ , \ r=d\dfrac{v^2+u^2}2$$

枚举 $d$ ，就可以得到 $u^2+v^2$ ，再枚举 $u$ 就可以统计答案了。

不过这样算出来的是第一象限内的解，所以最后答案要 $\times 4$ ；还要算上 $4$ 个坐标轴上的点。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll r;

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

inline ll work(ll x)
{
    ll ans=0;
    for (ll u=1;u*u*2<x;u++)
    {
        ll v=sqrt(x-u*u);
        if (v*v==x-u*u && gcd(u,v)==1) ans++;
    }
    return ans;
}

signed main()
{
    r=read()<<1;
    ll ans=0;
    for (ll d=1;d*d<=r;d++)
    {
        if (r%d) continue;
        ans+=work(d);
        if (d*d!=r) ans+=work(r/d);
    }
    printf("%lld",ans*4+4);
    return 0;
}