CodeVS/3119

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
高精度练习之大整数开根	★☆☆☆☆	答案正确	100	2015-2-4 14:13:40	超时（80）

题意

高精度开根号。

题解

• 还是高精度乘法+二分搞定，就是压位4位会T，这里压到9位（lld）就A了（一般到5-6位可能就够了，谁让我写的常数大sigh）
• 据说还可以手动开方，参见：http://blog.csdn.net/u011328276/article/details/9463885

代码

3119.cpp代码已折叠 展开折叠内容

#include<iostream> #include<iomanip> #include<algorithm> #include<vector> #include<cstdio> #define NNN 1000000000 #define nnn 9 using namespace std; class unsigned_huge_int { public: const size_t size() const { return u.size(); } friend const bool operator <(const unsigned_huge_int &a,const unsigned_huge_int &b) { if(a.size()==b.size()) { for(int i=a.size()-1;i>=0;--i){ if(a.u[i]!=b.u[i]) return a.u[i]<b.u[i]; } return 0; } return a.size()<b.size(); } friend const bool operator ==(const unsigned_huge_int &a,const unsigned_huge_int &b) { if(a.size()==b.size()) { for(int i=a.size()-1;i>=0;--i){ if(a.u[i]!=b.u[i]) return 0; } return 1; } return 0; } friend const bool operator <=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return a<b || a==b; } friend const bool operator >(const unsigned_huge_int &a,const unsigned_huge_int &b) { return !(a<=b); } friend const bool operator >=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return !(a<b); } friend const bool operator !=(const unsigned_huge_int &a,const unsigned_huge_int &b) { return a==b; } unsigned_huge_int() { u.clear(); u.push_back(0); } unsigned_huge_int(const unsigned long long &number) { u.clear(); u.push_back(number); refresh(); } unsigned_huge_int(const string&original) { u.clear(); for(int i=original.size()-1,j=0,p=1;i>=0;--i) { j+=(original[i]-'0')*p; p*=10; if((!i) || p==NNN) { u.push_back(j); j=0; p=1; } } } friend istream& operator >> (istream& os,unsigned_huge_int &ob) { string original; os>>original; ob=original; return os; } friend ostream& operator << (ostream& os,const unsigned_huge_int &ob) { os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1]; for(int i=ob.size()-2;i>=0;--i) os<<setw(nnn)<<setfill('0')<<ob.u[i]; return os; } friend const unsigned_huge_int operator +(const unsigned_huge_int &a,const unsigned_huge_int &b) { unsigned_huge_int r; r.u.resize(max(a.size(),b.size())); for(int i=0;i<r.size();++i) { if(i<a.size()) r.u[i]+=a.u[i]; if(i<b.size()) r.u[i]+=b.u[i]; } r.refresh(); return r; } const unsigned_huge_int d() { return *this+*this; } friend const unsigned_huge_int operator *(const unsigned_huge_int &a,const unsigned_huge_int &b) { if(b==2) return a+a; unsigned_huge_int r; r.u.resize(a.size()+b.size()); for(int i=0;i<a.size();++i) { for(int j=0;j<b.size();++j) { r.u[i+j]+=a.u[i]*b.u[j]; } } r.refresh(); return r; } friend const unsigned_huge_int operator -(const unsigned_huge_int &a,const unsigned_huge_int &b) { unsigned_huge_int r; const unsigned_huge_int *p1=&a,*p2=&b; if(*p1<*p2) swap(p1,p2); r.u.resize(p1->size()); for(int i=0;i<r.size();++i) if(i<p2->size()) r.u[i]+=p1->u[i]-p2->u[i]; else r.u[i]+=p1->u[i]; r.refresh(); return r; } friend unsigned_huge_int sqrt(const unsigned_huge_int &a) { unsigned_huge_int left=0,right=a,mid=0; while(left+1<right) { mid=div(left+right); if(a<mid*mid) right=mid; else left=mid; } return left; } friend unsigned_huge_int div(unsigned_huge_int a) { for(int i=a.size()-1;i>=0;--i)//fixed:i不可以unsigned// { if(a.u[i]%2&&i>=1) { a.u[i-1]+=NNN; } a.u[i]/=2; // cout<<"{"<<a.u[i]<<"}"; } a.refresh(); return a; } private: vector<unsigned long long> u; void refresh() { for(int i=0;i<size();++i) { if(u[i]>=NNN) { if(i==size()-1) u.push_back(u[i]/NNN); else u[i+1]+=u[i]/NNN; u[i]%=NNN; } while(u[i]<0) { u[i]+=NNN; u[i+1]-=1; } } for(int i=size()-1;i!=0;--i) { if(u[i]==0&&size()!=1) { u.pop_back(); }else{ break; } } } }; int main() { unsigned_huge_int a; cin>>a; cout<<sqrt(a); }