[ HAOI 2008 ] 圆上的整点

\(\\\)

Description

给出一个整数 \(r\) ，求圆 \(x^2+y^2=r^2\) 上的整点数。

\(r\le 2\times 10^9\)

\(\\\)

Solution

神题。

可以注意到，坐标轴上共有四个整点，其余位置各个象限里整点数相同，所以我们只需要计算第一象限的答案。

首先有方程

\[x^2+y^2=r^2
\]

移项，得

\[x^2=r^2-y^2=(r+y)(r-y)
\]

设 \(d=gcd(r+y,r-y)\)，有

\[x^2=\frac{r+y}{d}\times \frac{r-y}{d}\times d^2
\]

因为 \(x^2,d^2\) 均为完全平方数，所以 \(\frac{r+y}{d}\times \frac{r-y}{d}\) 是完全平方数。

根据 \(d\) 的定义，显然有 \((\frac{r+y}{d},\frac{r-y}{d})=1\)。

然而显然存在的是，两个不同的质数之积，或一个质数的平方和另一个质数的积都不是完全平方数。

所以 \(\frac{r+y}{d}, \frac{r-y}{d}\) 都是完全平方数。

我们设 \(a,b\) 分别满足：

\[a^2=\frac{r+y}{d},b^2= \frac{r-y}{d}
\]

那么有

\[a^2+b^2=\frac{r+y}{d}+\frac{r-y}{d}=\frac{2r}{d}
\]

解法出来了。

首先 \(\sqrt {2r}\) 枚举 \(2r\) 的因数，显然 \(d\) 不同的方案得到的点一定不同。

然后对于枚举的每一个 \(d\) ，枚举每一个可能的 \(a\) ，检验对应的 \(b\) 是否为整数，且满足互质即可。

注意交换 \(a,b\) 是一种情况，所以我们枚举 \(a\) 的范围在 \([1,\sqrt{\frac{2r}{d\times 2}}\ ]\) 里。

复杂度分析：

枚举约数 \(\sqrt{2r}\) ，对于每一个 \(d\) 再 \(\sqrt d\) 的枚举约数，验证用到 \(gcd\) 复杂度 \(log\) 。

总复杂度大概是 \((2r)^{\frac 34}log(2r)\) 级别的。

\(\\\)

Code

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

typedef long long ll;

ll n,ans;

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

int main(){

  scanf("%lld",&n);

  n<<=1;

  ll lim=sqrt(n);

  for(R ll d=1,lim1;d<=lim;++d)

    if(n%d==0){

      lim1=sqrt((n/d)/2);

      for(R ll a=1,b;a<=lim1;++a){

        b=sqrt((n/d)-a*a);

        if(a==b) continue;

        if(b*b!=(n/d)-a*a) continue;

        if(gcd(a*a,b*b)!=1) continue;

        ++ans;

      }

      if(n/d!=d){

        ll d1=n/d;

        lim1=sqrt(d/2);

        for(R ll a=1,b;a<=lim1;++a){

          b=sqrt((n/d1)-a*a);

          if(a==b) continue;

          if(b*b!=(n/d1)-a*a) continue;

          if(gcd(a*a,b*b)!=1) continue;

          ++ans;

        }

      }

    }

  printf("%lld\n",ans*4+4);

  return 0;

}

巴特西

[ HAOI 2008 ] 圆上的整点

Description

Solution

Code

最新文章

热门文章