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

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

【题解】

好久没有刷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;
}

 

https://sample-quest 说:
2023年4月14日 23:23

Board Sample Question Paper 2023 Aspirants who had Registered for the Board Exam can Download the Previous Paper When Board Announces the Dates to Download the Sample Paper. https://sample-questions-paper.in/ Board Sample Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Sample Paper.


登录 *


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