HAOI2008 圆上的整点

早上没有干劲来颓blog，结果被教练抓去打比赛，一直咕到下午

假设我们已经求得$x^2+y^2=r^2$的所有正整数解$ans$

那么我们很容易就可以发现每个象限都有到原点距离等于正整数解的这么多点

再算上坐标轴上一定会存在的4个点,那么答案就是$ans*4+4$

---

现在考虑如何快速求出$x^2+y^2=r^2$的所有正整数解

这时我们引入勾股方程的概念

勾股方程即形如$a^2+b^2=c^2$的方程

本题中已知$c^2$的值

一个事实是勾股方程的所有正整数解都可以被表示为下图的形式

$$1.1:a=\frac{d(u^2-v^2)}{2},b=duv,c=\frac{d(u^2+v^2)}{2}(gcd(u,v)=1)$$

也就是说每个勾股数组都可以由下面的式子同时乘一个数变换过来

$$1.2:a=\frac{u^2-v^2}{2},b=uv,c=\frac{u^2+v^2}{2}(gcd(u,v)=1)$$

这是为什么呢，考虑所有的勾股方程的整数解都是一个勾股数组，那么肯定可以被表示成如下的形式

$$1.3:a=u^2-v^2,b=4uv,c=u^2+v^2$$

所以假如式子$1.2$中的$a,b,c$的$gcd=1$，那么我们就可以用它不重不漏的表示出所有的勾股数组

证明左转洛谷日报-勾股数组

既然$1.1$可以不重不漏的表示出所有的解，那么我们就可以枚举$d$求出答案

具体步骤如下：

首先枚举$d\mid2r$,那么$u^2+v^2=2r/d$
接下来枚举$u$,验证$u$是否合法(如果存在$u^2+v^2=2r/d$并且$gcd(u,v)=1$则合法)，如果合法答案加一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
ll ans=0,r;
ll gcd(ll a,ll b)
{
    return !b?a:gcd(b,a%b);
}
bool check(ll u,ll V)
{
    int v=(ll)(sqrt(V));
    if(V==v*v)return gcd(u,v)==1;
    return 0;
}
ll calc(ll x)
{
    ll tmp=0;
    for(ll u=1;u*u*2<x;u++)
        tmp+=check(u,x-u*u);
    return tmp;
}
int main()
{
    scanf("%lld",&r);
    for(ll 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;
}