首页 > 代码库 > BZOJ 1041: [HAOI2008]圆上的整点
BZOJ 1041: [HAOI2008]圆上的整点
Sol
数学.
\(x^2+y^2=r^2\)
\(y^2=r^2-x^2\)
\(y^2=(r-x)(r+x)\)
令 \(d=(r-x,r+x)\)
\(r-x=du^2,r+x=dv^2\)
\(2r=d(u^2+v^2),(v,u)==1\)
\(y^2=d^2u^2v^2\)
然后枚举 \(d\) 再枚举 \(u\)
Code
/************************************************************** Problem: 1041 User: BeiYu Language: C++ Result: Accepted Time:80 ms Memory:1300 kb****************************************************************/ #include<cstdio>#include<cmath>#include<algorithm>#include<iostream>using namespace std; typedef long long LL; LL r,n,ans; inline LL in(LL x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; } LL calc(LL d){ LL res=0,m=n/d; for(LL u=1,v;2*u*u<=m;u++){ v=sqrt(m-u*u)+0.5; if(v<=u) break; if(v*v+u*u==m&&__gcd(u,v)==1) res++; }return res;}int main(){// freopen("in.in","r",stdin); r=in(),n=r<<1; for(LL d=1;d*d<=n;d++) if(n%d==0){ if(d*d==n) ans+=calc(d); else ans+=calc(d)+calc(n/d); } cout<<ans*4+4<<endl; return 0;}
BZOJ 1041: [HAOI2008]圆上的整点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。