BZOJ 1041 [HAOI2008] 圆上的整点 【数学】

tonyfang posted @ 2016年5月05日 16:45 in BZOJ with tags C++ OI , 385 阅读

【题解】

好久没有刷bzoj了,吃特色菜跪了所以就回来了……

题目:求$x^2+y^2=r^2$的$(x,y)$个数

$y^2=r^2-x^2=(r-x) \times (r+x)$

$let \quad d = gcd(r-x, r+x)$

$y^2=d^2 \times \frac{r+x}{d} \times \frac{r-x}{d}$

$A=\frac{r+x}{d}, B=\frac{r-x}{d}$

$y^2=d^2 \times A \times B$

由于$gcd(A,B)=1$且$A!=B$

所以A和B均为完全平方数,设$A=a^2,B=b^2$,则

$A+B=\frac{2r}{d}$

$a^2+b^2=\frac{2r}{d}$

所以d是2r的因数

那么我们先枚举d然后枚举a就好啦

时间复杂度:O(能过)

 

# include <stdio.h>
# include <math.h> 
# include <iostream>
using namespace std;

/*
x^2+y^2=r^2
y^2=(r-x)(r+x)
d=gcd(r-x, r+x)
y^2=d^2*(r+x)/d*(r-x)/d
A=(r+x)/d, B=(r-x)/d
y^2=d^2*A*B
A!=B && gcd(A, B)=1
==> A和B都是完全平方数

A=a^2, B=b^2
A+B=2r/d
a^2+b^2=2r/d
d是2r的因数……
枚举d,枚举a……
完啦 
*/

long long r, ans=0;

inline long long gcd (long long a, long long b) {
	long long r;
	while(b!=0) {
		r=a%b;
		a=b;
		b=r;
	}
	return a;
} 

inline void chk(int x) {
	long long to = sqrt(x/2), sqra, sqrb, b;
	for (long long a=1; a<=to; ++a) {
		sqra = a*a, sqrb = x - sqra, b = sqrt(sqrb); 
		if(b*b == sqrb && gcd(sqra, sqrb) == 1 && sqra != sqrb) ans++;
	}
}

int main() {	
	cin >> r;
	long long to = sqrt(r*2); 
	for (long long i=1; i<=to; ++i) {
		if(2*r%i != 0) continue; 
		chk(i);
		chk(2*r/i); 
	}
	ans=(ans+1)*4; 
	cout << ans << endl;
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter