bzoj 1041: [HAOI2008]圆上的整点 本原勾股數組

1041: [HAOI2008]圆上的整点

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2027  Solved: 853
[Submit][Status]

Description

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

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

HINT

n<=2000 000 000

Source

這道題可用本原勾股數組解，由於本原勾股數組(x,y,z),x^2+y^2==z且gcd(x,y)==gcd(x,z)==gcd(y,z)==1可表示爲

　　x=a^2-b^2

　　z=a^2+b^2

本題已知z，那麼我們可以先sqrt(n)枚舉n的因數z，再sqrt(z)枚舉a，統計即可。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 1100

#define MAXV MAXN*2

#define MAXE MAXV*2

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

inline int nextInt()

{

        char ch;

        int x=;

        bool flag=false;

        do

                ch=getchar(),flag=(ch=='-')?true:flag;

        while(ch<''||ch>'');

        do x=x*+ch-'';

        while (ch=getchar(),ch<='' && ch>='');

        return x*(flag?-:);

}

qword n,m,nn;

qword gcd(qword x,qword y)

{

        return (x%y==)?y:gcd(y,x%y);

}

int count(qword n)

{

        qword x,y;

        if (n==)

        {

        //        cout<<"0 "<<nn<<endl;

                return ;

        }

        qword l=ceil(sqrt(n));

        int ans=;

        for (x=;x<l;x++)

        {

                y=sqrt(n-x*x);

                if (x*x+y*y!=n)continue;

                if (x>=y)break;

                if (gcd(y*y-x*x,*y*y)!=)continue;

        //        cout<<(y*y-x*x)*(nn/n)<<" "<<2*x*y*(nn/n)<<endl;

        //        cout<<2*x*y*(nn/n)<<" "<<(y*y-x*x)*(nn/n)<<endl;

                ans+=+(x&&y);

        }

        return ans*;

}

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int i,j,k;

        int x,y,z;

        scanf(LL,&n);

        nn=n;

        qword ans=;

        qword l=ceil(sqrt(n));

        for (i=;i<l;i++)

        {

                if (n%i==)

                {

                        ans+=count(i);

                        ans+=count(n/i);

                }

        }

        if (l*l==n)ans+=count(l);

        printf(LL"\n",ans);

        return ;

}