题解 P2508 【[HAOI2008]圆上的整点】

Nemlit

2019-01-19 22:43:24

Solution

题目的所求可以转化为: $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; } ```