bzoj 1041 圆上的整点

Posted on | Views:

有技巧的大力枚举.

  • 求 $x^2+y^2=r^2$ 的整数解组数,只需要求出 $x,y>0$ 的组数,再 $\times 4,+4$ 即为答案.
  • 方程变形得到 $y^2=(r+x)(r-x)$ ,记 $d=gcd(r+x,r-x)$ ,则 $y^2=d^2\cdot \frac {r+x} d \cdot \frac {r-x} d$ .
  • 记 $u^2=\frac {r+x} d,v^2=\frac {r-x} d,u>v>0$ .则 $2r=d(u^2+v^2),2x=d(u^2-v^2),y=uvd$ .
  • 因为 $d$ 是 $2r$ 的约数,所以大力枚举 $d$ ,再大力枚举 $u$ ,计算出 $v$ 后再验证 $u>v$ 及 $gcd(u,v)=1$ 是否成立即可.
  • 时间复杂度 $O(r^{3\over 4} \cdot \log r)​$ .实际上跑不满,因为枚举 $d​$ 是 $O(r^{1\over 2})​$ 的,而只有 $d​$ 为 $2r​$ 约数时才枚举 $u​$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
ll gcd(ll a,ll b)
{
	if(!b)
		return a;
	return gcd(b,a%b);
}
int check(ll r,ll d,ll u)
{
	ll v2=2*r/d-u*u;
	ll v=sqrt(v2);
	if(v*v!=v2)
		return 0;
	if(u<=v)
		return 0;
	ll x=d*(u*u-v*v);
	if(x&1)
		return 0;
	x/=2;
	if(gcd(u,v)!=1)
		return 0;
	return 1;
}
int main()
{
	ll r=read();
	ll ans=0;
	for(ll d=1;d*d<=2*r;++d)
	{
		if(2*r%d==0)
		{
			for(ll u=1;u*u<2*r/d;++u)
				ans+=check(r,d,u);
			ll D=2*r/d;
			if(D!=d)
			{
				for(ll u=1;u*u<2*r/D;++u)
					ans+=check(r,D,u);
			}
		}
	}
	ans*=4;
	ans+=4;
	cout<<ans<<endl;
	return 0;
}