BZOJ 1041 数学

思路：

$x^2+y^2=r^2$
$y=\sqrt{(r+x)(r-x)}$
令$ d=gcd(r+x,r-x)$
设A=$(r-x)/d$　　 $B=(r+x)/d$
则$gcd(A,B)=1$
$y^2=d^2*A*B$
∵$d、y$为完全平方数、$gcd(A,B)=1$、且$A!=B$（在坐标轴上的最后算）
∴$A、B$为完全平方数
设$a^2=(r+x)/d　　b^2=(r-x)/d$
则$a^2+b^2=2r/d$
即d是2r的约数
那我们就$1到\sqrt{2r}$枚举约数
再枚举a （从$\sqrt{r/d}$枚举到$\sqrt{2r/d}$） $a^2=(r+x)/d$
$b^2=(r-x)/d=2r/d-a^2$
判断一下$gcd(a^2,b^2)$是不是等于1且$a!=b!=0$且$\sqrt{b}^2==b$
最后答案就是ans*4(四个象限)+4(坐标轴上的)

//By SiriusRen

#include <cmath>

#include <cstdio>

using namespace std;

#define int long long

int r,ans;

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

void solve(int d){

    int lst=sqrt(*r/d),fst=sqrt(r/d);

    if(fst*fst<r/d)fst++;

    for(int a=fst;a<=lst;a++){

        int sqrb=*r/d-a*a,b=sqrt(sqrb);

        if(a&&b&&b*b==sqrb&&a!=b&&gcd(a*a,sqrb)==)ans++;

    }

}

signed main(){

    scanf("%lld",&r);

    int sqr=sqrt(*r);

    for(int d=;d<=sqr;d++)if((*r)%d==)solve(d),solve(*r/d);

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

}

巴特西

BZOJ 1041 数学

最新文章

热门文章