首页 > 代码库 > bzoj 1041: [HAOI2008]圆上的整点 本原勾股數組
bzoj 1041: [HAOI2008]圆上的整点 本原勾股數組
1041: [HAOI2008]圆上的整点
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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*bz=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]圆上的整点 本原勾股數組
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。