bzoj 1041: [HAOI2008]圆上的整点 数学

1041: [HAOI2008]圆上的整点

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=1041

Description

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

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

HINT

n<=2000 000 000

题意

题解：

http://hzwer.com/1457.html

代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

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

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 2000001

#define mod 10007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

ll r,ans;

ll gcd(ll a,ll b)

{

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

}

int check(ll y,double x)

{

    if(x==floor(x))

    {

        ll x1=(ll)floor(x);

        if(gcd(x1*x1,y*y)==&&x1*x1!=y*y)

            return ;

    }

    return ;

}

int main()

{

    r=read();

    for(ll i=;i<=sqrt(*r);i++)

    {

        if((*r)%i==)

        {

            for(ll a=;a<=sqrt(r/i);a++)

            {

                double b=sqrt(((*r)/i)-a*a);

                if(check(a,b))

                    ans++;

            }

            if(i!=(*r)/i)

            {

                for(ll a=;a<=sqrt(i/);a++)

                {

                    double b=sqrt(i-a*a);

                    if(check(a,b))

                        ans++;

                }

            }

        }

    }

    cout<<ans*+<<endl;

}