Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
解题报告: 化简\(a^2+b^2=r^2\)\(a^2=(r+b)(r-b)\) 提出(r+b)和(r-b)的公因子d\(a^2=d^2*(r+b)/d*(r-b)/d\) 此时(r+b)/d和(r-b)/d 互质，所以两者都为完全平方数 所以令p,q分别为两者的平方根 可以得出\(p^2+q^2=2r/d\) 找出这样的搭配个数即是答案,所以枚举d和p，check(q)即可 这样求出的是第一象限的答案，最后再乘四加四即可
#include#include #include #include #include #include #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std;typedef long long ll;ll gcd(ll x,ll y){ return x%y?gcd(y,x%y):y;}void work(){ ll n,t,tmp,ans=0,x,y,lim; cin>>n;n<<=1;lim=sqrt(n); for(int i=1;i<=lim;i++){ if(n%i)continue; t=n/i;tmp=sqrt(t/2); for(int j=1;j<=tmp;j++){ x=t-j*j;y=sqrt(x); if(!x)continue; if(y*y==x && x!=j*j && gcd(x,j*j)==1) ans++; } if(i==t)continue; tmp=sqrt(i/2); for(int j=1;j<=tmp;j++){ x=i-j*j;y=sqrt(x); if(!x)continue; if(y*y==x && x!=j*j && gcd(x,j*j)==1) ans++; } } printf("%lld\n",(ans<<2)+4);}int main(){ work(); return 0;}
