【BZOJ】【1041】【HAOI2008】圆周上的点

数学


  orz hzwer

  完全不会做……

  很纠结啊,如果将来再遇到这种题,还是很难下手啊……

引用题解:

【分析】:

样例图示:

【BZOJ】【1041】【HAOI2008】圆周上的点

首先,最暴力的算法显而易见:枚举x轴上的每个点,带入圆的方程,检查是否算出的值是否为整点,这样的枚举量为2*N,显然过不了全点。

然后想数学方法。

【BZOJ】【1041】【HAOI2008】圆周上的点

【BZOJ】【1041】【HAOI2008】圆周上的点

有了上面的推理,那么实现的方法为:

枚举d∈[1,sqrt(2R)],然后根据上述推理可知:必先判d是否为2R的一约数。

此时d为2R的约数有两种情况:d=d或d=2R/d。

第一种情况:d=2R/d。枚举a∈[1,sqrt(2R/2d)] <由2*a*a < 2*R/d转变来>,算出对应的b=sqrt(2R/d-a^2),检查是否此时的A,B满足:A≠B且A,B互质 <根据上面的推理可知必需满足此条件>,若是就将答案加1

第二种情况:d=d。枚举a∈[1,sqrt(d/2)] <由2*a*a < d转变来>,算出对应的b=sqrt(d-a^2),检查是否此时的A,B满足:A≠B且A,B互质 <根据上面的推理可知必需满足此条件>,若是就将答案加1

因为这样只算出了第一象限的情况<上面枚举时均是从1开始枚举>,根据圆的对称性,其他象限的整点数与第一象限中的整点数相同,最后,在象限轴上的4个整点未算,加上即可,那么最后答案为ans=4*第一象限整点数+4

【时间复杂度分析】:

枚举d:O(sqrt(2R)),然后两次枚举a:O(sqrt(d/2))+O(sqrt(R/d)),求最大公约数:O(logN)

 /**************************************************************
Problem: 1041
User: Tunix
Language: C++
Result: Accepted
Time:192 ms
Memory:816 kb
****************************************************************/ //BZOJ 1000
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
typedef double lf;
/******************tamplate*********************/
LL r,ans;
LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
bool check(LL y,lf x){
if (x==floor(x)){
LL x1=x;
if (gcd(x1*x1,y*y)== && x1*x1!=y*y)
return ;
}
return false;
}
int main(){
scanf("%lld",&r);
for(LL d=;d<=sqrt(*r);d++)
if (*r%d==){
for(LL a=;a<=(LL)sqrt(*r/(*d));a++){
lf b=sqrt((*r)/d-a*a);
if (check(a,b))ans++;
}
if (d!=*r/d){
for(LL a=;a<=(LL)sqrt(d/);a++){
lf b=sqrt(d-a*a);
if (check(a,b))ans++;
}
}
}
printf("%lld\n",ans*+);
return ;
}

1041: [HAOI2008]圆上的整点

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2376  Solved: 1019
[Submit][Status][Discuss]

Description

求一个给定的圆(x^2+y^2=r^2),在圆周上有多少个点的坐标是整数。

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

HINT

n<=2000 000 000

Source

[Submit][Status][Discuss]

上一篇:解决spring boot启动报错java.lang.NoClassDefFoundError: ch/qos/logback/classic/Level


下一篇:数据结构 - 归并排序(merging sort)