[HAOI2008]圆上的整点(数论)

题目的所求可以转化为:

\(y^2=r^2-x^2\)(其中r,x,y均为整数)

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

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

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

则有\(y^2=d^2*s^2*v^2\),即\(y=d*s*v\)

②-①得\(x=\frac{ t^2-s^2 }{2}*d\)

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

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

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

注意:小心乘法运算时爆longlong

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read()
{
re int x=0,f=1;re char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return x*f;
}
il int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
int r,ans;
il void work(int d)
{
for(re 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(re 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;
}
上一篇:VLAN的三种类型及三种属性


下一篇:Codeforces Round #302 (Div. 1)