数学

　　orz hzwer

　　完全不会做……

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

引用题解：

【分析】：

样例图示：

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

然后想数学方法。

有了上面的推理，那么实现的方法为：

枚举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

Output

整点个数

Sample Input

Sample Output

HINT

n<=2000 000 000

Source

[Submit][Status][Discuss]

巴特西

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

数学