【BZOJ1041】[HAOI2008]圆上的整点

题面

bzoj

洛谷

题解

不妨设\(x>0,y>0\)

\[x^2+y^2=r^2\\
y^2=(x+r)(x-r)
\]

设\(r-x=ud,r+x=vd,(u,v)=1\)

\[y^2=d^2uv
\]

\(u,v\)一定为完全平方数

则\(u=s^2,v=t^2\)且必有\((s,t)=1\)

\[2r=(u+v)d=(s^2+t^2)d\\
\Rightarrow\\
x=\frac{t^2-s^2}{2}d\\
y=dst\
\]

然后枚举\(2r\)的约数即可

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

ll R, ans;

int main () {

	cin >> R;

	for (ll i = 1; i * i <= 2 * R; i++) {

		if (2 * R % i == 0) {

			ll d = i;

			for (ll s = 1; s * s <= 2 * R / d; s++) {

				ll t = sqrt(2 * R / d - s * s);

				if (s * s + t * t == 2 * R / d && __gcd(s, t) == 1) {

					ll x = (t * t - s * s) / 2 * d, y = d * s * t;

					if (x > 0 && y > 0 && x * x + y * y == R * R) ans += 2;

				}

			}

			if (i * i != R) {

			    d = 2 * R / i;

			    for (ll s = 1; s * s <= 2 * R / d; s++) {

				    ll t = sqrt(2 * R / d - s * s);

				    if (s * s + t * t == 2 * R / d && __gcd(s, t) == 1) {

					    ll x = (t * t - s * s) / 2 * d, y = d * s * t;

					    if (x > 0 && y > 0 && x * x + y * y == R * R) ans += 2;

				    }

			    }

		    }

		}

	}

	printf("%lld\n", (ans + 1) * 4);

	return 0;

}