1041: [HAOI2008]圆上的整点

1041: [HAOI2008]圆上的整点

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4298  Solved: 1944
[Submit][Status][Discuss]

Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

Input

只有一个正整数n,n<=2000 000 000

Output

整点个数

Sample Input

4

Sample Output

4

HINT

科普视频

/*

* @Author: lyuc

*/

/*

 题意：就是求有多少斜边为n的勾股数;

 思路：y*y=r*r-x*x

          =(r-x)*(r+x)

       令

        d=GCD(r-x,r+x)

       那么

        r-x=d*u*u

        r+x=d*v*v

        并且GCD(u,v)==1

        得到

        r=d*(u*u+v*v)/2

        y=d*d*u*u*v*v

        x=d*(v*v-u*u)

        这样枚举r的因子，在枚举u，注意x,y,r的范围就可以了

*/

#include <bits/stdc++.h>

#define LL long long

using namespace std;

LL r;

LL res;

LL gcd(LL a,LL b){ return b==?a:gcd(b,a%b); }

void cal(LL d){

    LL v;

    for(LL u=;u<=sqrt(*r*1.0/d);u++){

        v=(LL)sqrt( (*r*1.0/d-u*u)*1.0 );

        if(gcd(u,v)==&&u<=v&&d*(u*u+v*v)==*r){

            res++;

        }

    }

}

int main(int argc, char *argv[])

{

    //freopen("in.txt","r",stdin);

    res=;

    scanf("%lld",&r);

    for(LL i=;i<=sqrt(*r*1.0);i++){

        if(*r%i==){

            if((LL)i*i==*r){

                cal(i);

            }else{

                cal(i);

                cal(*r/i);

            }

        }

    }

    printf("%lld\n",res*);

    return ;

}