题解 P2508 【[HAOI2008]圆上的整点】
Nemlit
2019-01-19 22:43:24
题目的所求可以转化为:
$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;
}
```