摘要

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

题意

高精度开根号。

题解

代码

3119.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<cstdio>
  6. #define NNN 1000000000
  7. #define nnn 9
  8. using namespace std;
  9. class unsigned_huge_int
  10. {
  11. public:
  12. const size_t size() const
  13. {
  14. return u.size();
  15. }
  16. friend const bool operator <(const unsigned_huge_int &a,const unsigned_huge_int &b)
  17. {
  18. if(a.size()==b.size())
  19. {
  20. for(int i=a.size()-1;i>=0;--i){
  21. if(a.u[i]!=b.u[i])
  22. return a.u[i]<b.u[i];
  23. }
  24. return 0;
  25. }
  26. return a.size()<b.size();
  27. }
  28. friend const bool operator ==(const unsigned_huge_int &a,const unsigned_huge_int &b)
  29. {
  30. if(a.size()==b.size())
  31. {
  32. for(int i=a.size()-1;i>=0;--i){
  33. if(a.u[i]!=b.u[i])
  34. return 0;
  35. }
  36. return 1;
  37. }
  38. return 0;
  39. }
  40. friend const bool operator <=(const unsigned_huge_int &a,const unsigned_huge_int &b)
  41. {
  42. return a<b || a==b;
  43. }
  44. friend const bool operator >(const unsigned_huge_int &a,const unsigned_huge_int &b)
  45. {
  46. return !(a<=b);
  47. }
  48. friend const bool operator >=(const unsigned_huge_int &a,const unsigned_huge_int &b)
  49. {
  50. return !(a<b);
  51. }
  52. friend const bool operator !=(const unsigned_huge_int &a,const unsigned_huge_int &b)
  53. {
  54. return a==b;
  55. }
  56. unsigned_huge_int()
  57. {
  58. u.clear();
  59. u.push_back(0);
  60. }
  61. unsigned_huge_int(const unsigned long long &number)
  62. {
  63. u.clear();
  64. u.push_back(number);
  65. refresh();
  66. }
  67. unsigned_huge_int(const string&original)
  68. {
  69. u.clear();
  70. for(int i=original.size()-1,j=0,p=1;i>=0;--i)
  71. {
  72. j+=(original[i]-'0')*p;
  73. p*=10;
  74. if((!i) || p==NNN)
  75. {
  76. u.push_back(j);
  77. j=0;
  78. p=1;
  79. }
  80. }
  81. }
  82. friend istream& operator >> (istream& os,unsigned_huge_int &ob)
  83. {
  84. string original;
  85. os>>original;
  86. ob=original;
  87. return os;
  88. }
  89. friend ostream& operator << (ostream& os,const unsigned_huge_int &ob)
  90. {
  91. os<<setw(0)<<setfill('0')<<ob.u[ob.size()-1];
  92. for(int i=ob.size()-2;i>=0;--i)
  93. os<<setw(nnn)<<setfill('0')<<ob.u[i];
  94. return os;
  95. }
  96. friend const unsigned_huge_int operator +(const unsigned_huge_int &a,const unsigned_huge_int &b)
  97. {
  98. unsigned_huge_int r;
  99. r.u.resize(max(a.size(),b.size()));
  100. for(int i=0;i<r.size();++i)
  101. {
  102. if(i<a.size())
  103. r.u[i]+=a.u[i];
  104. if(i<b.size())
  105. r.u[i]+=b.u[i];
  106. }
  107. r.refresh();
  108. return r;
  109. }
  110. const unsigned_huge_int d()
  111. {
  112. return *this+*this;
  113. }
  114. friend const unsigned_huge_int operator *(const unsigned_huge_int &a,const unsigned_huge_int &b)
  115. {
  116. if(b==2)
  117. return a+a;
  118. unsigned_huge_int r;
  119. r.u.resize(a.size()+b.size());
  120. for(int i=0;i<a.size();++i)
  121. {
  122. for(int j=0;j<b.size();++j)
  123. {
  124. r.u[i+j]+=a.u[i]*b.u[j];
  125. }
  126. }
  127. r.refresh();
  128. return r;
  129. }
  130. friend const unsigned_huge_int operator -(const unsigned_huge_int &a,const unsigned_huge_int &b)
  131. {
  132. unsigned_huge_int r;
  133. const unsigned_huge_int *p1=&a,*p2=&b;
  134. if(*p1<*p2)
  135. swap(p1,p2);
  136. r.u.resize(p1->size());
  137. for(int i=0;i<r.size();++i)
  138. if(i<p2->size())
  139. r.u[i]+=p1->u[i]-p2->u[i];
  140. else
  141. r.u[i]+=p1->u[i];
  142. r.refresh();
  143. return r;
  144. }
  145. friend unsigned_huge_int sqrt(const unsigned_huge_int &a)
  146. {
  147. unsigned_huge_int left=0,right=a,mid=0;
  148. while(left+1<right)
  149. {
  150. mid=div(left+right);
  151. if(a<mid*mid)
  152. right=mid;
  153. else
  154. left=mid;
  155. }
  156. return left;
  157. }
  158. friend unsigned_huge_int div(unsigned_huge_int a)
  159. {
  160. for(int i=a.size()-1;i>=0;--i)//fixed:i不可以unsigned//
  161. {
  162. if(a.u[i]%2&&i>=1)
  163. {
  164.  
  165. a.u[i-1]+=NNN;
  166. }
  167. a.u[i]/=2;
  168. // cout<<"{"<<a.u[i]<<"}";
  169. }
  170. a.refresh();
  171. return a;
  172. }
  173. private:
  174. vector<unsigned long long> u;
  175. void refresh()
  176. {
  177. for(int i=0;i<size();++i)
  178. {
  179. if(u[i]>=NNN)
  180. {
  181. if(i==size()-1)
  182. u.push_back(u[i]/NNN);
  183. else
  184. u[i+1]+=u[i]/NNN;
  185. u[i]%=NNN;
  186. }
  187. while(u[i]<0)
  188. {
  189. u[i]+=NNN;
  190. u[i+1]-=1;
  191. }
  192. }
  193. for(int i=size()-1;i!=0;--i)
  194. {
  195. if(u[i]==0&&size()!=1)
  196. {
  197. u.pop_back();
  198. }else{
  199. break;
  200. }
  201. }
  202. }
  203. };
  204.  
  205.  
  206.  
  207. int main()
  208. {
  209. unsigned_huge_int a;
  210. cin>>a;
  211. cout<<sqrt(a);
  212. }

著作权声明[编辑]

关于[编辑]