[关闭]
@zzzc18 2018-01-26T08:19:06.000000Z 字数 3885 阅读 433

高精度

高精度 模板库


其实高精度就按你平时手算的的方法写出来就好了
这份代码用
高精乘可以用FFT优化(这里没有)
高精除需要使用 的幂次来试商,这样会快很多

其实这东西要的就是一个,一般用到高精的东西最后不是别的地方错了,而是高精错了。


  1. #include<vector>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. namespace Super_Calc{
  7. typedef long long LL;
  8. const int WIDTH = 10000+9;
  9. const int MOD = 100000000;
  10. char BUF[WIDTH];
  11. struct Num{
  12. vector<LL> vec;
  13. };
  14. struct PAIR{
  15. Num first;
  16. bool second;
  17. };
  18. Num Input(){
  19. Num re;
  20. scanf("%s",BUF);
  21. int len=strlen(BUF);
  22. for(int i=len-1;i>=7;i-=8){
  23. LL tmp=0;
  24. for(int j=7;j>=0;j--)
  25. tmp=tmp*10+BUF[i-j]-'0';
  26. re.vec.push_back(tmp);
  27. }
  28. len=len%8;
  29. if(len==0)return re;
  30. LL tmp=0;
  31. for(int i=0;i<=len-1;i++)
  32. tmp=tmp*10+BUF[i]-'0';
  33. re.vec.push_back(tmp);
  34. return re;
  35. }
  36. void Print(const Num &A,char s=0,bool sign=1){
  37. if(!sign)putchar('-');
  38. sprintf(BUF,"%lld",A.vec.back());
  39. printf("%s",BUF);
  40. for(int i=A.vec.size()-2;i>=0;i--){
  41. sprintf(BUF,"%08lld",A.vec[i]);
  42. printf("%s",BUF);
  43. }
  44. if(s)putchar(s);
  45. }
  46. Num Change(LL val){
  47. Num re;
  48. re.vec.push_back(val);
  49. return re;
  50. }
  51. Num operator << (const Num &A,int k){
  52. Num re;
  53. re.vec.resize(A.vec.size()+k);
  54. for(int i=k,j=0;j<A.vec.size();i++,j++){
  55. re.vec[i]=A.vec[j];
  56. }
  57. return re;
  58. }
  59. bool operator < (const Num &A,const Num &B){
  60. if(A.vec.size()!=B.vec.size())
  61. return A.vec.size()<B.vec.size();
  62. int len=A.vec.size();
  63. for(int i=len-1;i>=0;i--){
  64. if(A.vec[i]<B.vec[i])return true;
  65. if(A.vec[i]>B.vec[i])return false;
  66. }
  67. return false;
  68. }
  69. bool operator <= (const Num &A,const Num &B){
  70. if(A.vec.size()!=B.vec.size())
  71. return A.vec.size()<B.vec.size();
  72. int len=A.vec.size();
  73. for(int i=len-1;i>=0;i--){
  74. if(A.vec[i]<B.vec[i])return true;
  75. if(A.vec[i]>B.vec[i])return false;
  76. }
  77. return true;
  78. }
  79. bool operator > (const Num &A,const Num &B){
  80. if(A.vec.size()!=B.vec.size())
  81. return A.vec.size()>B.vec.size();
  82. int len=A.vec.size();
  83. for(int i=len-1;i>=0;i--){
  84. if(A.vec[i]>B.vec[i])return true;
  85. if(A.vec[i]<B.vec[i])return false;
  86. }
  87. return false;
  88. }
  89. bool operator >= (const Num &A,const Num &B){
  90. if(A.vec.size()!=B.vec.size())
  91. return A.vec.size()>B.vec.size();
  92. int len=A.vec.size();
  93. for(int i=len-1;i>=0;i--){
  94. if(A.vec[i]>B.vec[i])return true;
  95. if(A.vec[i]<B.vec[i])return false;
  96. }
  97. return true;
  98. }
  99. bool operator == (const Num &A,const Num &B){
  100. if(A.vec.size()!=B.vec.size())
  101. return false;
  102. int len=A.vec.size();
  103. for(int i=0;i<len;i++)
  104. if(A.vec[i]!=B.vec[i])return false;
  105. return true;
  106. }
  107. Num operator + (const Num &A,const Num &B){
  108. Num re;
  109. re.vec.resize(max(A.vec.size(),B.vec.size())+1);
  110. for(int i=0;i<A.vec.size();i++){
  111. re.vec[i]+=A.vec[i];
  112. }
  113. for(int i=0;i<B.vec.size();i++){
  114. re.vec[i]+=B.vec[i];
  115. }
  116. for(int i=0;i<re.vec.size()-1;i++){
  117. re.vec[i+1]+=re.vec[i]/MOD;
  118. re.vec[i]%=MOD;
  119. }
  120. while(!re.vec.back() && re.vec.size()>1) re.vec.pop_back();
  121. return re;
  122. }
  123. PAIR operator - (const Num &A,const Num &B){
  124. Num X,Y;
  125. bool pd;
  126. if(A==B){X.vec.push_back(0);return (PAIR){X,1};}
  127. if(A>B){X=A;Y=B;pd=1;}
  128. else{X=B;Y=A;pd=0;}
  129. for(int i=0;i<Y.vec.size();i++){
  130. X.vec[i]-=Y.vec[i];
  131. }
  132. for(int i=0;i<X.vec.size()-1;i++){
  133. if(X.vec[i]<0){
  134. X.vec[i]+=MOD;
  135. X.vec[i+1]--;
  136. }
  137. }
  138. while(!X.vec.back() && X.vec.size()>1)X.vec.pop_back();
  139. return (PAIR){X,pd};
  140. }
  141. Num operator * (const Num &A,const Num &B){
  142. Num re;
  143. re.vec.resize(A.vec.size()+B.vec.size()+1);
  144. for(int i=0,lim=A.vec.size();i<lim;i++){
  145. for(int j=0,lim=B.vec.size();j<lim;j++){
  146. re.vec[i+j]+=A.vec[i]*B.vec[j];
  147. }
  148. }
  149. for(int i=0,lim=re.vec.size();i<lim;i++){
  150. re.vec[i+1]+=re.vec[i]/MOD;
  151. re.vec[i]%=MOD;
  152. }
  153. while(!re.vec.back() && re.vec.size()>1) re.vec.pop_back();
  154. return re;
  155. }
  156. Num DivMod(const Num &A,const Num &B,Num &R){
  157. R=A;
  158. Num re;
  159. re.vec.resize(A.vec.size()-B.vec.size()+1);
  160. for(int i=re.vec.size()-1;i>=0;i--){
  161. Num val10=B<<i;
  162. for(int j=26;j>=0;j--){
  163. LL tmp=1<<j;
  164. Num val2=val10*Change(tmp);
  165. if(R>=val2){
  166. R=(R-val2).first;
  167. re.vec[i]+=tmp;
  168. }
  169. }
  170. }
  171. while(!re.vec.back() && re.vec.size()>1) re.vec.pop_back();
  172. return re;
  173. }
  174. Num operator / (const Num &A,const Num &B){
  175. Num re;
  176. if(A==B){re.vec.push_back(1);return re;}
  177. if(A<B){re.vec.push_back(0);return re;}
  178. Num X;
  179. re=DivMod(A,B,X);
  180. return re;
  181. }
  182. Num operator % (const Num &A,const Num &B){
  183. Num re;
  184. if(A==B){re.vec.push_back(0);return re;}
  185. if(A<B){return A;}
  186. Num X;
  187. DivMod(A,B,X);
  188. return X;
  189. }
  190. }
  191. using namespace Super_Calc;
  192. int main(){
  193. Num A=Input();
  194. Num B=Input();
  195. Print(A+B,'\n');
  196. PAIR C=A-B;
  197. Print(C.first,'\n',C.second);
  198. Print(A*B,'\n');
  199. Print(A/B,'\n');
  200. Print(A%B,'\n');
  201. return 0;
  202. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注