洛谷P2508 [HAOI2008]圆上的整点

题目描述

求一个给定的圆$ (x2=r^2) $，在圆周上有多少个点的坐标是整数。

输入格式

$r$

输出格式

整点个数

输入输出样例

输入

输出

说明/提示

$n\le 2000 000 000$

思路

题目的所求可以转化为

问题的所求可以转化为$y^{2}=r^2-x^2$(其中$x,y,r$均为正整数).

即$y^2=(r-x)(r+x)$(其中$r,x,y$均为正整数)

不妨设$(r-x)=d\times u------① (r+x)=d\times v------②($其中$gcd(u,v)=1$)

则有$y^2=d^2\times u \times v$,因为$u,v$互质所以$u,v$一定是完全平方数,所以再设$u=s^2,v=t^2$

则有$y^2=d^2 \times s^2 \times v^2$,即$y=d \times s \times v$

$②-①$得$x=\dfrac{t^2-s^2}{2}\times d$

$②+①$得$2\times r=(t^2+s^2)\times d$

然后枚举$2\times r$的约数$d$,枚举算出$s$,算出对应$t$,若$gcd(t,s)=1$且$x,t$为整数,带入求出$x,y$,若符合题意答案就加二($x,y$满足交换律)

最后的答案为$(ans+1)\times 4$,($+1$是因为坐标轴上有一点,$\times 4$是因为$4$个象限)

注意:小心乘法运算时爆$long$ $long$;

代码如下:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<string>

#include<iomanip>

#include<cstdlib>

#include<queue>

#include<stack>

#include<map>

#include<vector>

#include<set>

#define int long long

inline int read()

{

   int s=0,w=1;

   char ch=getchar();

   while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}

   while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();

   return s*w;

}

inline int gcd(int a,int b)

{

    if(!b) return a;

    return gcd(b,a%b);

}

int r,ans;

inline void work(int d)

{

    for(int s=1;s*s<=r/d;++s)

    {

        int t=sqrt(r/d-s*s);

        if(gcd(s,t)==1&&s*s+t*t==r/d)

        {

            int x=(s*s-t*t)/2*d;

            int y=d*s*t;

            if(x>0&&y>0&&x*x+y*y==(r/2)*(r/2)) ans+=2;

        }

    }

}

signed main()

{

    r=read()*2;

    for(int i=1;i*i<=r;++i)

    {

        if(r%i==0)

        {

            work(i);

            if(i*i!=r) work(r/i);

        }

    }

    printf("%lld",(1+ans)*4);

    return 0;

}