首页 > 代码库 > BZOJ 4544: 椭圆上的整点
BZOJ 4544: 椭圆上的整点
Sol
数学.
跟圆上的整点一样...TA写了个积性函数的算法...以后再说吧...
\(x^2+3y^2=r^2\)
\(3y^2=r^2-x^2\)
\(3y^2=(r-x)(r+x)\)
\(y^2=\frac{1}{3}(r-x)(r+x)\)
\(d=(r-x)(r+x)\)
\(r-x=3du^2,r+x=dv^2\) 这里 \(r-x\) 和 \(r+x\) 并没有什么区别.
\(2r=d(3u^2+v^2)\)
枚举 \(d\) 和 \(u\)
感觉复杂度是\(O(n^{\frac{3}{4}})\)
但是可以跑最大数据的说.
Code
/************************************************************** Problem: 4544 User: BeiYu Language: C++ Result: Accepted Time:8568 ms Memory:1300 kb****************************************************************/ #include<cstdio>#include<cmath>#include<algorithm>#include<vector>#include<utility>#include<iostream>using namespace std; typedef long long LL;#define debug(a) cout<<#a<<"="<<a<<" "#define mpr(a,b) make_pair(a,b) LL T,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; } vector<pair<LL,LL> > p; LL calc(LL d){ LL res=0,m=n/d;// cout<<"*************"<<endl;// debug(m),debug(d);cout<<endl; for(LL u=1,v;u*u*3<=m;u++){ v=sqrt(m-3*u*u+0.5);// debug(u),debug(v),debug(3*v*v+u*u),cout<<endl;// if(u>v) break; if(v*v+u*u*3==m&&__gcd(v*v,u*u*3)==1) res++;// cout<<"get!",debug(d*u*u*3),debug(d*v*v),debug(d*u*u*3+d*v*v)<<endl;// p.push_back(mpr(d*u*u*3,d*v*v)); }return res;}int main(){// freopen("in.in","r",stdin); for(T=in();T--;){ r=in(),n=r<<1,ans=0; 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+2<<endl;// sort(p.begin(),p.end());// for(int i=0;i<p.size();i++) cout<<p[i].first<<" "<<p[i].second<<endl; } return 0;}
BZOJ 4544: 椭圆上的整点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。