首页 > 代码库 > bzoj 1041: [HAOI2008]圆上的整点 本原勾股數組

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

  y=2*a*b

  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 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;inline int nextInt(){        char ch;        int x=0;        bool flag=false;        do                ch=getchar(),flag=(ch==-)?true:flag;        while(ch<0||ch>9);        do x=x*10+ch-0;        while (ch=getchar(),ch<=9 && ch>=0);        return x*(flag?-1:1);}qword n,m,nn;qword gcd(qword x,qword y){        return (x%y==0)?y:gcd(y,x%y);}int count(qword n){        qword x,y;        if (n==1)        {        //        cout<<"0 "<<nn<<endl;                return 4;        }        qword l=ceil(sqrt(n));        int ans=0;        for (x=1;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,2*y*y)!=1)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+=1+(x&&y);        }        return ans*4;}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=0;        qword l=ceil(sqrt(n));        for (i=1;i<l;i++)        {                if (n%i==0)                {                        ans+=count(i);                        ans+=count(n/i);                }        }        if (l*l==n)ans+=count(l);        printf(LL"\n",ans);        return 0;}

 

 

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