洛谷P2508 [HAOI2008]圆上的整点

题目描述

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

输入格式

(r)

输出格式

整点个数

输入输出样例

输入

4

输出

4

说明/提示

(nle 2000 000 000)

思路

题目的所求可以转化为
问题的所求可以转化为(y^{2}=r^2-x^2)(其中(x,y,r)均为正整数).
即(y^2=(r-x)(r+x))(其中(r,x,y)均为正整数)
不妨设((r-x)=d imes u------① (r+x)=d imes v------②()其中(gcd(u,v)=1))
则有(y^2=d^2 imes u imes v),因为(u,v)互质所以(u,v)一定是完全平方数,所以再设(u=s^2,v=t^2)
则有(y^2=d^2 imes s^2 imes v^2),即(y=d imes s imes v)
(②-①)得(x=dfrac{t^2-s^2}{2} imes d)
(②+①)得(2 imes r=(t^2+s^2) imes d)
然后枚举(2 imes r)的约数(d),枚举算出(s),算出对应(t),若(gcd(t,s)=1)且(x,t)为整数,带入求出(x,y),若符合题意答案就加二((x,y)满足交换律)
最后的答案为((ans+1) imes 4),((+1)是因为坐标轴上有一点,( imes 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;
}