Description：

给出一个整数 $r$ ，求圆 $x^2+y^2=r^2$ 上的整点数。

$1\leqslant r\leqslant 2\times10^9$

Solution：

这种题，肯定是推一下式子然后暴力枚举某个东西判断合法的。 $$ x^2=r^2-y^2=(r+y)(r-y) $$ 设 $d=\gcd(r+y,r-y)$ ： $$ x^2=\frac{r+y}d\times \frac{r-y}d\times d^2 $$ 因为 $x^2,d^2$ 均为完全平方数，且 $\frac{r+y}d,\frac{r-y}d$ 互质，所以他们也必须都是完全平方数，设 $a^2=\frac{r+y}d,b^2=\frac{r-y}d$ ： $$ a^2+b^2=\frac{r+y}d+\frac{r-y}d=\frac{2r}d $$ 然后我们可以 $O(\sqrt{2r})$ 枚举 $2r$ 的约数 $d$ ，再枚举 $a$ ，判断 $\frac{2r}d-a^2$ 是否是平方数，以及 $a^2$ 和 $b^2$ 是否互质。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll r;

ll fac[1000000],tot = 0;

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

int main()

{

	scanf("%lld",&r);

	for(ll d = 1;d * d <= 2 * r;++d)

	{

		if((2 * r % d) == 0)

		{

			fac[++tot] = d;

			if(d * d != 2 * r)fac[++tot] = 2 * r / d;

		}

	}

	ll ans = 0;

	for(ll i = 1;i <= tot;++i)

	{

		ll d = fac[i];

		for(ll a = 1;a * a <= 2 * r / d;++a)

		{

			ll b2 = 2 * r / d - a * a;

			if((ll)sqrt(b2) * sqrt(b2) == b2 && gcd(b2,a * a) == 1)

			{

				if(d * a * sqrt(b2) >= 0 && r - b2 * d >= 0)

				{

					++ans;

				}

			}

		}

	}

	cout << (ans - 1) * 4 << endl;

	return 0;

}