2021.12.06 P2508 [HAOI2008]圆上的整点（数论+ \(\pi\) ）
https://www.luogu.com.cn/problem/P2508
题意：
求一个给定的圆 \((x^2+y^2=R^2)\) ，在圆周上有多少个点的坐标是整数。
分析：
第一步，咱把圆以横竖坐标轴为分界线分成四份儿，算出一份的整点坐标数*4就是结果。
恭喜你，40分到手。
第二步，先画一个 \(R=5\) 的圆，只关注第一象限，这里有四个整点坐标，分别为 \((0,5)\) ， \((3,4)\) ， \((4,3)\) ， \((5,0)\) 。有没有发现这四个点关于直线 \(y=x\) 对称。更新一下算法，由 \(x^2+y^2=R^2\) 得： \(x=\sqrt{R^2-y^2}\) ，则当 \(x=y=\sqrt{R^2-y^2}\) 时，这个 \(\frac{1}{4}\) 圆在 \((x,y)\) 这个点上对称。所以咱只需要算 \(\frac{1}{8}\) 个圆就行啦，记得处理 \(x==y\) 且 \(x\) 与 \(y\) 均为整点的情况，这个时候在边界上的话要只算一次。
恭喜恭喜，60分就这么来了~
第三步，进入推公式大法 。
\[y^2=R^2-x^2\\
y^2=(R-x)*(R+x)\\
设u*d=R-x,v*d=R+x,d=\gcd(u,v)\\
则\gcd(u,v)=1\\
y^2=d^2*u*v\\
因为y^2、d^2均为完全平方数，则u*v为完全平方数\\
因为\gcd(u,v)=1，则可设u=s^2,v=t^2\\
y^2=d^2*s^2*t^2\\
则y=d*s*t\\
2*x=(R+x)-(R-x)\\
=d*(v-u)\\
=d*(t^2-s^2)\\
x=d*\frac{t^2-s^2}{2}
\]
好啦，100分到手~
挂上大家推荐的视频
https://www.bilibili.com/video/av12131743/
虽然我并没有看懂……
代码如下：
40pts：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
int r,ans;
signed main(){
IOS;
cin>>r;
int x=0,y=r;
for(;x<=r;x++){
while(x*x+y*y>r*r&&y>0)--y;
if(x*x+y*y==r*r)++ans;//,cout<<x<<" "<<y<<endl;
//cout<<x<<" "<<y<<endl;
}
cout<<ans*4-4;
return 0;
}
60pts：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
int r,ans;
signed main(){
IOS;
cin>>r;
int x=0,y=r;
int len=sqrt((double)(r*r)/2.0);
//cout<<r<<" "<<len<<endl;
for(;x<=len;x++){
while(x*x+y*y>r*r&&y>0)--y;
if(x*x+y*y==r*r)++ans;//,cout<<x<<" "<<y<<endl;
//cout<<x<<" "<<y<<endl;
}
ans*=2;
if(len*len*2==r*r)--ans;
cout<<ans*4-4;
return 0;
}
100pts：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
int R,ans;
inline int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
inline void calc(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=(t*t-s*s)/2*d;
int y=d*s*t;
if(x>0&&y>0&&x*x+y*y==R/2*R/2)ans+=2;
}
}
}
signed main(){
IOS;
cin>>R;R*=2;
for(int i=1;i*i<=R;i++)if(R%i==0){
calc(i);
if(R%i!=i)calc(R/i);
}
cout<<ans*4+4;
return 0;
}
