1. 首页
  2. 文章中心
  3. =========基本数据结构==========

ACM-高精度模板(综合篇)

56 阅读 0 评论
我是靠谱客的博主 腼腆硬币，最近开发中收集的这篇文章主要介绍ACM-高精度模板(综合篇)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转载地址：https://blog.csdn.net/u013615904/article/details/43373601

在这里，我们约定，能用int表示的数据视为单精度，否则为高精度。所有函数的设计均采用带返回值的形式。

本文包含

1.高精度加法

2.高精度减法

3.高精度乘法

1）高精度乘高精度的朴素算法

2）高精度乘高精度FFT优化算法

3）高精度乘单精度

4.高精度除法

1）高精度除高精度

2）高精度除单精度

5.高精度取模

1）高精度对高精度取模

2）高精度对单精度取模

6.高精度阶乘

7.高精度幂

8.高精度GCD

9.高精度进制转换

10.高精度求平方根

下面切入正题

1.高精度加法

传入参数约定：传入参数均为string类型，返回值为string类型

算法思想：倒置相加再还原。

算法复杂度：o(n)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=110;  
  6. string add(string a,string b)//只限两个非负整数相加  
  7. {  
  8.     string ans;  
  9.     int na[L]={0},nb[L]={0};  
  10.     int la=a.size(),lb=b.size();  
  11.     for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';  
  12.     for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';  
  13.     int lmax=la>lb?la:lb;  
  14.     for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;  
  15.     if(na[lmax]) lmax++;  
  16.     for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';  
  17.     return ans;  
  18. }  
  19. int main()  
  20. {  
  21.     string a,b;  
  22.     while(cin>>a>>b) cout<<add(a,b)<<endl;  
  23.     return 0;  
  24. }  

2.高精度减法

传入参数约定：传入参数均为string类型，返回值为string类型

算法思想：倒置相减再还原。

算法复杂度：o(n)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=110;  
  6. string sub(string a,string b)//只限大的非负整数减小的非负整数  
  7. {  
  8.     string ans;  
  9.     int na[L]={0},nb[L]={0};  
  10.     int la=a.size(),lb=b.size();  
  11.     for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';  
  12.     for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';  
  13.     int lmax=la>lb?la:lb;  
  14.     for(int i=0;i<lmax;i++)  
  15.     {  
  16.         na[i]-=nb[i];  
  17.         if(na[i]<0) na[i]+=10,na[i+1]--;  
  18.     }  
  19.     while(!na[--lmax]&&lmax>0)  ;lmax++;  
  20.     for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';  
  21.     return ans;  
  22. }  
  23. int main()  
  24. {  
  25.     string a,b;  
  26.     while(cin>>a>>b) cout<<sub(a,b)<<endl;  
  27.     return 0;  
  28. }  

3.高精度乘法

1）高精度乘高精度的朴素算法

传入参数约定：传入参数均为string类型，返回值为string类型

算法思想：倒置相乘，然后统一处理进位，再还原。

算法复杂度：o(n^2)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=110;  
  6. string mul(string a,string b)//高精度乘法a,b,均为非负整数  
  7. {  
  8.     string s;  
  9.     int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积  
  10.     fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0  
  11.     for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数  
  12.     for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';  
  13.     for(int i=1;i<=La;i++)  
  14.         for(int j=1;j<=Lb;j++)  
  15.         nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）  
  16.     for(int i=1;i<=La+Lb;i++)  
  17.         nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位  
  18.     if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0  
  19.     for(int i=La+Lb-1;i>=1;i--)  
  20.         s+=nc[i]+'0';//将整形数组转成字符串  
  21.     return s;  
  22. }  
  23. int main()  
  24. {  
  25.     string a,b;  
  26.     while(cin>>a>>b) cout<<mul(a,b)<<endl;  
  27.     return 0;  
  28. }  

2）高精度乘高精度FFT优化算法

传入参数约定：传入参数均为string类型，返回值为string类型

算法思想：将两个高精度乘数每个数位上的数视为多项式对应的系数，用o(n*log(n))的复杂度转成点值形式，再利用o(n)的复杂度相乘，最后对点值进行差值，用o(n*log(n))的复杂度还原成多项式的形式，即原来的形式。

算法复杂度：o(n*log(n))

[cpp] view plain copy
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <algorithm>  
  4. #include <cstring>  
  5. #include <cmath>  
  6. #include <map>  
  7. #include <queue>  
  8. #include <set>  
  9. #include <vector>  
  10. using namespace std;  
  11. #define L(x) (1 << (x))  
  12. const double PI = acos(-1.0);  
  13. const int Maxn = 133015;  
  14. double ax[Maxn], ay[Maxn], bx[Maxn], by[Maxn];  
  15. char sa[Maxn/2],sb[Maxn/2];  
  16. int sum[Maxn];  
  17. int x1[Maxn],x2[Maxn];  
  18. int revv(int x, int bits)  
  19. {  
  20.     int ret = 0;  
  21.     for (int i = 0; i < bits; i++)  
  22.     {  
  23.         ret <<= 1;  
  24.         ret |= x & 1;  
  25.         x >>= 1;  
  26.     }  
  27.     return ret;  
  28. }  
  29. void fft(double * a, double * b, int n, bool rev)  
  30. {  
  31.     int bits = 0;  
  32.     while (1 << bits < n) ++bits;  
  33.     for (int i = 0; i < n; i++)  
  34.     {  
  35.         int j = revv(i, bits);  
  36.         if (i < j)  
  37.             swap(a[i], a[j]), swap(b[i], b[j]);  
  38.     }  
  39.     for (int len = 2; len <= n; len <<= 1)  
  40.     {  
  41.         int half = len >> 1;  
  42.         double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);  
  43.         if (rev) wmy = -wmy;  
  44.         for (int i = 0; i < n; i += len)  
  45.         {  
  46.             double wx = 1, wy = 0;  
  47.             for (int j = 0; j < half; j++)  
  48.             {  
  49.                 double cx = a[i + j], cy = b[i + j];  
  50.                 double dx = a[i + j + half], dy = b[i + j + half];  
  51.                 double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;  
  52.                 a[i + j] = cx + ex, b[i + j] = cy + ey;  
  53.                 a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;  
  54.                 double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;  
  55.                 wx = wnx, wy = wny;  
  56.             }  
  57.         }  
  58.     }  
  59.     if (rev)  
  60.     {  
  61.         for (int i = 0; i < n; i++)  
  62.             a[i] /= n, b[i] /= n;  
  63.     }  
  64. }  
  65. int solve(int a[],int na,int b[],int nb,int ans[])  
  66. {  
  67.     int len = max(na, nb), ln;  
  68.     for(ln=0; L(ln)<len; ++ln);  
  69.     len=L(++ln);  
  70.     for (int i = 0; i < len ; ++i)  
  71.     {  
  72.         if (i >= na) ax[i] = 0, ay[i] =0;  
  73.         else ax[i] = a[i], ay[i] = 0;  
  74.     }  
  75.     fft(ax, ay, len, 0);  
  76.     for (int i = 0; i < len; ++i)  
  77.     {  
  78.         if (i >= nb) bx[i] = 0, by[i] = 0;  
  79.         else bx[i] = b[i], by[i] = 0;  
  80.     }  
  81.     fft(bx, by, len, 0);  
  82.     for (int i = 0; i < len; ++i)  
  83.     {  
  84.         double cx = ax[i] * bx[i] - ay[i] * by[i];  
  85.         double cy = ax[i] * by[i] + ay[i] * bx[i];  
  86.         ax[i] = cx, ay[i] = cy;  
  87.     }  
  88.     fft(ax, ay, len, 1);  
  89.     for (int i = 0; i < len; ++i)  
  90.         ans[i] = (int)(ax[i] + 0.5);  
  91.     return len;  
  92. }  
  93. string mul(string sa,string sb)  
  94. {  
  95.     int l1,l2,l;  
  96.     int i;  
  97.     string ans;  
  98.     memset(sum, 0, sizeof(sum));  
  99.     l1 = sa.size();  
  100.     l2 = sb.size();  
  101.     for(i = 0; i < l1; i++)  
  102.         x1[i] = sa[l1 - i - 1]-'0';  
  103.     for(i = 0; i < l2; i++)  
  104.         x2[i] = sb[l2-i-1]-'0';  
  105.     l = solve(x1, l1, x2, l2, sum);  
  106.     for(i = 0; i<l || sum[i] >= 10; i++) // 进位  
  107.     {  
  108.         sum[i + 1] += sum[i] / 10;  
  109.         sum[i] %= 10;  
  110.     }  
  111.     l = i;  
  112.     while(sum[l] <= 0 && l>0)    l--; // 检索最高位  
  113.     for(i = l; i >= 0; i--)    ans+=sum[i] + '0'; // 倒序输出  
  114.     return ans;  
  115. }  
  116. int main()  
  117. {  
  118.     cin.sync_with_stdio(false);  
  119.     string a,b;  
  120.     while(cin>>a>>b) cout<<mul(a,b)<<endl;  
  121.     return 0;  
  122. }  

3）高精度乘单精度

传入参数约定：传入第一个参数为string类型，，第二个参数为int型，返回值为string类型

算法思想：倒置相乘，然后统一处理进位，再还原。

算法复杂度：o(n)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=100005;  
  6. int na[L];  
  7. string mul(string a,int b)//高精度a乘单精度b  
  8. {  
  9.     string ans;  
  10.     int La=a.size();  
  11.     fill(na,na+L,0);  
  12.     for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';  
  13.     int w=0;  
  14.     for(int i=0;i<La;i++) na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;  
  15.     while(w) na[La++]=w%10,w/=10;  
  16.     La--;  
  17.     while(La>=0) ans+=na[La--]+'0';  
  18.     return ans;  
  19. }  
  20. int main()  
  21. {  
  22.     string a;  
  23.     int b;  
  24.     while(cin>>a>>b) cout<<mul(a,b)<<endl;  
  25.     return 0;  
  26. }  


4.高精度除法

1）高精度除高精度

传入参数约定：传入第一第二个参数均为string类型，第三个为int型，返回值为string类型

算法思想：倒置，试商，高精度减法。

算法复杂度：o(n^2)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=110;  
  6. int sub(int *a,int *b,int La,int Lb)  
  7. {  
  8.     if(La<Lb) return -1;//如果a小于b，则返回-1  
  9.     if(La==Lb)  
  10.     {  
  11.         for(int i=La-1;i>=0;i--)  
  12.             if(a[i]>b[i]) break;  
  13.             else if(a[i]<b[i]) return -1;//如果a小于b，则返回-1  
  14.   
  15.     }  
  16.     for(int i=0;i<La;i++)//高精度减法  
  17.     {  
  18.         a[i]-=b[i];  
  19.         if(a[i]<0) a[i]+=10,a[i+1]--;  
  20.     }  
  21.     for(int i=La-1;i>=0;i--)  
  22.         if(a[i]) return i+1;//返回差的位数  
  23.     return 0;//返回差的位数  
  24.   
  25. }  
  26. string div(string n1,string n2,int nn)//n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数  
  27. {  
  28.     string s,v;//s存商,v存余数  
  29.      int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;//a，b是整形数组表示被除数，除数，tp保存被除数的长度  
  30.      fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);//数组元素都置为0  
  31.      for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';  
  32.      for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';  
  33.      if(La<Lb || (La==Lb && n1<n2)) {  
  34.             //cout<<0<<endl;  
  35.      return n1;}//如果a<b,则商为0，余数为被除数  
  36.      int t=La-Lb;//除被数和除数的位数之差  
  37.      for(int i=La-1;i>=0;i--)//将除数扩大10^t倍  
  38.         if(i>=t) b[i]=b[i-t];  
  39.         else b[i]=0;  
  40.      Lb=La;  
  41.      for(int j=0;j<=t;j++)  
  42.      {  
  43.          int temp;  
  44.          while((temp=sub(a,b+j,La,Lb-j))>=0)//如果被除数比除数大继续减  
  45.          {  
  46.              La=temp;  
  47.              r[t-j]++;  
  48.          }  
  49.      }  
  50.      for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位  
  51.      while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的  
  52.      while(i>=0) s+=r[i--]+'0';  
  53.      //cout<<s<<endl;  
  54.      i=tp;  
  55.      while(!a[i]) i--;//将整形数组表示的余数转化成字符串表示的</span>  
  56.      while(i>=0) v+=a[i--]+'0';  
  57.      if(v.empty()) v="0";  
  58.      //cout<<v<<endl;  
  59.      if(nn==1) return s;  
  60.      if(nn==2) return v;  
  61. }  
  62. int main()  
  63. {  
  64.     string a,b;  
  65.     while(cin>>a>>b) cout<<div(a,b,1)<<endl;  
  66.     return 0;  
  67. }  


1）高精度除单精度

传入参数约定：传入第一参数为string类型，第二个为int型，返回值为string类型

算法思想：模拟手工除法。

算法复杂度：o(n)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. string div(string a,int b)//高精度a除以单精度b  
  5. {  
  6.     string r,ans;  
  7.     int d=0;  
  8.     if(a=="0") return a;//特判  
  9.     for(int i=0;i<a.size();i++)  
  10.     {  
  11.             r+=(d*10+a[i]-'0')/b+'0';//求出商  
  12.             d=(d*10+(a[i]-'0'))%b;//求出余数  
  13.     }  
  14.     int p=0;  
  15.     for(int i=0;i<r.size();i++)  
  16.     if(r[i]!='0') {p=i;break;}  
  17.     return r.substr(p);  
  18. }  
  19. int main()  
  20. {  
  21.     string a;  
  22.     int b;  
  23.     while(cin>>a>>b)  
  24.     {  
  25.         cout<<div(a,b)<<endl;  
  26.     }  
  27.     return 0;  
  28. }  



5.高精度取模

1）高精度对高精度取模(以在高精度除高精度中实现，此处不再赘述)

2）高精度对单精度取模

传入参数约定：传入第一参数为string类型，第二个为int型，返回值为string类型

算法思想：利用(a+b)%c=a%c+b%c。

算法复杂度：o(n)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. int mod(string a,int b)//高精度a除以单精度b  
  5. {  
  6.     int d=0;  
  7.     for(int i=0;i<a.size();i++) d=(d*10+(a[i]-'0'))%b;//求出余数  
  8.     return d;  
  9. }  
  10. int main()  
  11. {  
  12.     string a;  
  13.     int b;  
  14.     while(cin>>a>>b)  
  15.     {  
  16.         cout<<mod(a,b)<<endl;  
  17.     }  
  18.     return 0;  
  19. }  
6.高精度阶乘

传入参数约定：传入参数为int型，返回值为string类型

算法思想：高精度乘单精度的简单运用。

算法复杂度：o(n^2)

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=100005;  
  6. int a[L];  
  7. string fac(int n)  
  8. {  
  9.     string ans;  
  10.     if(n==0) return "1";  
  11.     fill(a,a+L,0);  
  12.     int s=0,m=n;  
  13.     while(m) a[++s]=m%10,m/=10;  
  14.     for(int i=n-1;i>=2;i--)  
  15.     {  
  16.         int w=0;  
  17.         for(int j=1;j<=s;j++) a[j]=a[j]*i+w,w=a[j]/10,a[j]=a[j]%10;  
  18.         while(w) a[++s]=w%10,w/=10;  
  19.     }  
  20.     while(!a[s]) s--;  
  21.     while(s>=1) ans+=a[s--]+'0';  
  22.     return ans;  
  23. }  
  24. int main()  
  25. {  
  26.     int n;  
  27.     while(cin>>n) cout<<fac(n)<<endl;  
  28.     return 0;  
  29. }  


7.高精度幂

传入参数约定：传入第一参数为string类型，第二个为int型，返回值为string类型

算法思想：FFT高精乘+二分求幂。

算法复杂度：o(n*log(n)*log(m))

[cpp] view plain copy
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <algorithm>  
  4. #include <cstring>  
  5. #include <cmath>  
  6. #include <map>  
  7. #include <queue>  
  8. #include <set>  
  9. #include <vector>  
  10. using namespace std;  
  11. #define L(x) (1 << (x))  
  12. const double PI = acos(-1.0);  
  13. const int Maxn = 133015;  
  14. double ax[Maxn], ay[Maxn], bx[Maxn], by[Maxn];  
  15. char sa[Maxn/2],sb[Maxn/2];  
  16. int sum[Maxn];  
  17. int x1[Maxn],x2[Maxn];  
  18. int revv(int x, int bits)  
  19. {  
  20.     int ret = 0;  
  21.     for (int i = 0; i < bits; i++)  
  22.     {  
  23.         ret <<= 1;  
  24.         ret |= x & 1;  
  25.         x >>= 1;  
  26.     }  
  27.     return ret;  
  28. }  
  29. void fft(double * a, double * b, int n, bool rev)  
  30. {  
  31.     int bits = 0;  
  32.     while (1 << bits < n) ++bits;  
  33.     for (int i = 0; i < n; i++)  
  34.     {  
  35.         int j = revv(i, bits);  
  36.         if (i < j)  
  37.             swap(a[i], a[j]), swap(b[i], b[j]);  
  38.     }  
  39.     for (int len = 2; len <= n; len <<= 1)  
  40.     {  
  41.         int half = len >> 1;  
  42.         double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);  
  43.         if (rev) wmy = -wmy;  
  44.         for (int i = 0; i < n; i += len)  
  45.         {  
  46.             double wx = 1, wy = 0;  
  47.             for (int j = 0; j < half; j++)  
  48.             {  
  49.                 double cx = a[i + j], cy = b[i + j];  
  50.                 double dx = a[i + j + half], dy = b[i + j + half];  
  51.                 double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;  
  52.                 a[i + j] = cx + ex, b[i + j] = cy + ey;  
  53.                 a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;  
  54.                 double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;  
  55.                 wx = wnx, wy = wny;  
  56.             }  
  57.         }  
  58.     }  
  59.     if (rev)  
  60.     {  
  61.         for (int i = 0; i < n; i++)  
  62.             a[i] /= n, b[i] /= n;  
  63.     }  
  64. }  
  65. int solve(int a[],int na,int b[],int nb,int ans[])  
  66. {  
  67.     int len = max(na, nb), ln;  
  68.     for(ln=0; L(ln)<len; ++ln);  
  69.     len=L(++ln);  
  70.     for (int i = 0; i < len ; ++i)  
  71.     {  
  72.         if (i >= na) ax[i] = 0, ay[i] =0;  
  73.         else ax[i] = a[i], ay[i] = 0;  
  74.     }  
  75.     fft(ax, ay, len, 0);  
  76.     for (int i = 0; i < len; ++i)  
  77.     {  
  78.         if (i >= nb) bx[i] = 0, by[i] = 0;  
  79.         else bx[i] = b[i], by[i] = 0;  
  80.     }  
  81.     fft(bx, by, len, 0);  
  82.     for (int i = 0; i < len; ++i)  
  83.     {  
  84.         double cx = ax[i] * bx[i] - ay[i] * by[i];  
  85.         double cy = ax[i] * by[i] + ay[i] * bx[i];  
  86.         ax[i] = cx, ay[i] = cy;  
  87.     }  
  88.     fft(ax, ay, len, 1);  
  89.     for (int i = 0; i < len; ++i)  
  90.         ans[i] = (int)(ax[i] + 0.5);  
  91.     return len;  
  92. }  
  93. string mul(string sa,string sb)  
  94. {  
  95.     int l1,l2,l;  
  96.     int i;  
  97.     string ans;  
  98.     memset(sum, 0, sizeof(sum));  
  99.     l1 = sa.size();  
  100.     l2 = sb.size();  
  101.     for(i = 0; i < l1; i++)  
  102.         x1[i] = sa[l1 - i - 1]-'0';  
  103.     for(i = 0; i < l2; i++)  
  104.         x2[i] = sb[l2-i-1]-'0';  
  105.     l = solve(x1, l1, x2, l2, sum);  
  106.     for(i = 0; i<l || sum[i] >= 10; i++) // 进位  
  107.     {  
  108.         sum[i + 1] += sum[i] / 10;  
  109.         sum[i] %= 10;  
  110.     }  
  111.     l = i;  
  112.     while(sum[l] <= 0 && l>0)    l--; // 检索最高位  
  113.     for(i = l; i >= 0; i--)    ans+=sum[i] + '0'; // 倒序输出  
  114.     return ans;  
  115. }  
  116. string Pow(string a,int n)  
  117. {  
  118.     if(n==1) return a;  
  119.     if(n&1) return mul(Pow(a,n-1),a);  
  120.     string ans=Pow(a,n/2);  
  121.     return mul(ans,ans);  
  122. }  
  123. int main()  
  124. {  
  125.     cin.sync_with_stdio(false);  
  126.     string a;  
  127.     int b;  
  128.     while(cin>>a>>b) cout<<Pow(a,b)<<endl;  
  129.     return 0;  
  130. }  

8.高精度GCD

传入参数约定：传入参数均为string类型，返回值为string类型

算法思想：高精度加减乘除的运用。

算法复杂度：已无法估计。

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<algorithm>  
  4. using namespace std;  
  5. const int L=110;  
  6. string add(string a,string b)  
  7. {  
  8.     string ans;  
  9.     int na[L]={0},nb[L]={0};  
  10.     int la=a.size(),lb=b.size();  
  11.     for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';  
  12.     for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';  
  13.     int lmax=la>lb?la:lb;  
  14.     for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;  
  15.     if(na[lmax]) lmax++;  
  16.     for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';  
  17.     return ans;  
  18. }  
  19. string mul(string a,string b)  
  20. {  
  21.     string s;  
  22.     int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积  
  23.     fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0  
  24.     for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数  
  25.     for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';  
  26.     for(int i=1;i<=La;i++)  
  27.         for(int j=1;j<=Lb;j++)  
  28.         nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）  
  29.     for(int i=1;i<=La+Lb;i++)  
  30.         nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位  
  31.     if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0  
  32.     for(int i=La+Lb-1;i>=1;i--)  
  33.         s+=nc[i]+'0';//将整形数组转成字符串  
  34.     return s;  
  35. }  
  36. int sub(int *a,int *b,int La,int Lb)  
  37. {  
  38.     if(La<Lb) return -1;//如果a小于b，则返回-1  
  39.     if(La==Lb)  
  40.     {  
  41.         for(int i=La-1;i>=0;i--)  
  42.             if(a[i]>b[i]) break;  
  43.             else if(a[i]<b[i]) return -1;//如果a小于b，则返回-1  
  44.   
  45.     }  
  46.     for(int i=0;i<La;i++)//高精度减法  
  47.     {  
  48.         a[i]-=b[i];  
  49.         if(a[i]<0) a[i]+=10,a[i+1]--;  
  50.     }  
  51.     for(int i=La-1;i>=0;i--)  
  52.         if(a[i]) return i+1;//返回差的位数  
  53.     return 0;//返回差的位数  
  54.   
  55. }  
  56. string div(string n1,string n2,int nn)//n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数  
  57. {  
  58.     string s,v;//s存商,v存余数  
  59.      int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;//a，b是整形数组表示被除数，除数，tp保存被除数的长度  
  60.      fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);//数组元素都置为0  
  61.      for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';  
  62.      for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';  
  63.      if(La<Lb || (La==Lb && n1<n2)) {  
  64.             //cout<<0<<endl;  
  65.      return n1;}//如果a<b,则商为0，余数为被除数  
  66.      int t=La-Lb;//除被数和除数的位数之差  
  67.      for(int i=La-1;i>=0;i--)//将除数扩大10^t倍  
  68.         if(i>=t) b[i]=b[i-t];  
  69.         else b[i]=0;  
  70.      Lb=La;  
  71.      for(int j=0;j<=t;j++)  
  72.      {  
  73.          int temp;  
  74.          while((temp=sub(a,b+j,La,Lb-j))>=0)//如果被除数比除数大继续减  
  75.          {  
  76.              La=temp;  
  77.              r[t-j]++;  
  78.          }  
  79.      }  
  80.      for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位  
  81.      while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的  
  82.      while(i>=0) s+=r[i--]+'0';  
  83.      //cout<<s<<endl;  
  84.      i=tp;  
  85.      while(!a[i]) i--;//将整形数组表示的余数转化成字符串表示的</span>  
  86.      while(i>=0) v+=a[i--]+'0';  
  87.      if(v.empty()) v="0";  
  88.      //cout<<v<<endl;  
  89.      if(nn==1) return s;  
  90.      if(nn==2) return v;  
  91. }  
  92. bool judge(string s)//判断s是否为全0串  
  93. {  
  94.     for(int i=0;i<s.size();i++)  
  95.         if(s[i]!='0') return false;  
  96.     return true;  
  97. }  
  98. string gcd(string a,string b)//求最大公约数  
  99. {  
  100.     string t;  
  101.     while(!judge(b))//如果余数不为0，继续除  
  102.     {  
  103.         t=a;//保存被除数的值  
  104.         a=b;//用除数替换被除数  
  105.         b=div(t,b,2);//用余数替换除数  
  106.     }  
  107.     return a;  
  108. }  
  109. int main()  
  110. {  
  111.     cin.sync_with_stdio(false);  
  112.     string a,b;  
  113.     while(cin>>a>>b) cout<<gcd(a,b)<<endl;  
  114.     return 0;  
  115. }  


9.高精度进制转换

传入参数约定：传入第一个参数为string类型，第二第三均为int型，返回值为string类型

算法思想：模拟手工进制转换。

算法复杂度：o(n^2)。

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. //将字符串表示的10进制大整数转换为m进制的大整数  
  5. //并返回m进制大整数的字符串  
  6. bool judge(string s)//判断串是否为全零串  
  7. {  
  8.     for(int i=0;i<s.size();i++)  
  9.         if(s[i]!='0') return 1;  
  10.     return 0;  
  11. }  
  12. string solve(string s,int n,int m)//n进制转m进制只限0-9进制，若涉及带字母的进制，稍作修改即可  
  13. {  
  14.     string r,ans;  
  15.     int d=0;  
  16.     if(!judge(s)) return "0";//特判  
  17.     while(judge(s))//被除数不为0则继续  
  18.     {  
  19.         for(int i=0;i<s.size();i++)  
  20.         {  
  21.             r+=(d*n+s[i]-'0')/m+'0';//求出商  
  22.             d=(d*n+(s[i]-'0'))%m;//求出余数  
  23.         }  
  24.        s=r;//把商赋给下一次的被除数  
  25.        r="";//把商清空  
  26.         ans+=d+'0';//加上进制转换后数字  
  27.         d=0;//清空余数  
  28.     }  
  29.     reverse(ans.begin(),ans.end());//倒置下  
  30.     return ans;  
  31. }  
  32. int main()  
  33. {  
  34.     string s;  
  35.     while(cin>>s)  
  36.     {  
  37.         cout<<solve(s,10,7)<<endl;  
  38.     }  
  39.     return 0;  
  40. }  

10.高精度求平方根，思路就是二分+高精度加减乘除法

设数的长度为n，则需二分log(2,10^n)次即n*log(2,10) 约等于n*3.3，由于数的长度为n，朴素高精度乘法复杂度为o(n^2)。故朴素算法求解高精度平方根复杂度为O(n^3)

当然，你也可以用FFT优化下高精度乘法。

下面的代码实现了求大整数平方根的整数部分。

JAVA版

[java] view plain copy
  1. import java.io.*;  
  2. import java.math.*;  
  3. import java.util.*;  
  4. public class Main {  
  5.     static Scanner cin = new Scanner (new BufferedInputStream(System.in));  
  6.     public static BigInteger BigIntegerSqrt(BigInteger n){  
  7.         BigInteger l=BigInteger.ONE,r=n,mid,ans=BigInteger.ONE;  
  8.         while(l.compareTo(r)<=0){  
  9.             mid=l.add(r).divide(BigInteger.valueOf(2));  
  10.             if(mid.multiply(mid).compareTo(n)<=0){  
  11.                 ans=mid;  
  12.                 l=mid.add(BigInteger.ONE);  
  13.             }else{  
  14.                 r=mid.subtract(BigInteger.ONE);  
  15.             }  
  16.         }  
  17.         return ans;  
  18.     }  
  19.     public static void main(String args []){  
  20.         BigInteger n;  
  21.         int t;  
  22.         t= cin.nextInt();  
  23.         while(t > 0)  
  24.         {  
  25.             t--;  
  26.             n=cin.nextBigInteger();  
  27.             BigInteger ans=BigIntegerSqrt(n);  
  28.             System.out.println(ans);  
  29.         }  
  30.     }  
  31. }  


C++版

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<cstring>  
  3. #include<cstdio>  
  4. #include<algorithm>  
  5. using namespace std;  
  6. const int L=2015;  
  7. string add(string a,string b)//只限两个非负整数相加  
  8. {  
  9.     string ans;  
  10.     int na[L]={0},nb[L]={0};  
  11.     int la=a.size(),lb=b.size();  
  12.     for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';  
  13.     for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';  
  14.     int lmax=la>lb?la:lb;  
  15.     for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;  
  16.     if(na[lmax]) lmax++;  
  17.     for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';  
  18.     return ans;  
  19. }  
  20. string sub(string a,string b)//只限大的非负整数减小的非负整数  
  21. {  
  22.     string ans;  
  23.     int na[L]={0},nb[L]={0};  
  24.     int la=a.size(),lb=b.size();  
  25.     for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';  
  26.     for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';  
  27.     int lmax=la>lb?la:lb;  
  28.     for(int i=0;i<lmax;i++)  
  29.     {  
  30.         na[i]-=nb[i];  
  31.         if(na[i]<0) na[i]+=10,na[i+1]--;  
  32.     }  
  33.     while(!na[--lmax]&&lmax>0)  ;lmax++;  
  34.     for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';  
  35.     return ans;  
  36. }  
  37. string mul(string a,string b)//高精度乘法a,b,均为非负整数  
  38. {  
  39.     string s;  
  40.     int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积  
  41.     fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0  
  42.     for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数  
  43.     for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';  
  44.     for(int i=1;i<=La;i++)  
  45.         for(int j=1;j<=Lb;j++)  
  46.         nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）  
  47.     for(int i=1;i<=La+Lb;i++)  
  48.         nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位  
  49.     if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0  
  50.     for(int i=La+Lb-1;i>=1;i--)  
  51.         s+=nc[i]+'0';//将整形数组转成字符串  
  52.     return s;  
  53. }  
  54. int sub(int *a,int *b,int La,int Lb)  
  55. {  
  56.     if(La<Lb) return -1;//如果a小于b，则返回-1  
  57.     if(La==Lb)  
  58.     {  
  59.         for(int i=La-1;i>=0;i--)  
  60.             if(a[i]>b[i]) break;  
  61.             else if(a[i]<b[i]) return -1;//如果a小于b，则返回-1  
  62.   
  63.     }  
  64.     for(int i=0;i<La;i++)//高精度减法  
  65.     {  
  66.         a[i]-=b[i];  
  67.         if(a[i]<0) a[i]+=10,a[i+1]--;  
  68.     }  
  69.     for(int i=La-1;i>=0;i--)  
  70.         if(a[i]) return i+1;//返回差的位数  
  71.     return 0;//返回差的位数  
  72.   
  73. }  
  74. string div(string n1,string n2,int nn)//n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数  
  75. {  
  76.     string s,v;//s存商,v存余数  
  77.      int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;//a，b是整形数组表示被除数，除数，tp保存被除数的长度  
  78.      fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);//数组元素都置为0  
  79.      for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0';  
  80.      for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0';  
  81.      if(La<Lb || (La==Lb && n1<n2)) {  
  82.             //cout<<0<<endl;  
  83.      return n1;}//如果a<b,则商为0，余数为被除数  
  84.      int t=La-Lb;//除被数和除数的位数之差  
  85.      for(int i=La-1;i>=0;i--)//将除数扩大10^t倍  
  86.         if(i>=t) b[i]=b[i-t];  
  87.         else b[i]=0;  
  88.      Lb=La;  
  89.      for(int j=0;j<=t;j++)  
  90.      {  
  91.          int temp;  
  92.          while((temp=sub(a,b+j,La,Lb-j))>=0)//如果被除数比除数大继续减  
  93.          {  
  94.              La=temp;  
  95.              r[t-j]++;  
  96.          }  
  97.      }  
  98.      for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;//统一处理进位  
  99.      while(!r[i]) i--;//将整形数组表示的商转化成字符串表示的  
  100.      while(i>=0) s+=r[i--]+'0';  
  101.      //cout<<s<<endl;  
  102.      i=tp;  
  103.      while(!a[i]) i--;//将整形数组表示的余数转化成字符串表示的</span>  
  104.      while(i>=0) v+=a[i--]+'0';  
  105.      if(v.empty()) v="0";  
  106.      //cout<<v<<endl;  
  107.      if(nn==1) return s;  
  108.      if(nn==2) return v;  
  109. }  
  110. bool cmp(string a,string b)  
  111. {  
  112.     if(a.size()<b.size()) return 1;//a小于等于b返回真  
  113.     if(a.size()==b.size()&&a<=b) return 1;  
  114.     return 0;  
  115. }  
  116. string BigInterSqrt(string n)  
  117. {  
  118.     string l="1",r=n,mid,ans;  
  119.     while(cmp(l,r))  
  120.     {  
  121.         mid=div(add(l,r),"2",1);  
  122.         if(cmp(mul(mid,mid),n)) ans=mid,l=add(mid,"1");  
  123.         else r=sub(mid,"1");  
  124.     }  
  125.     return ans;  
  126. }  
  127. string DeletePreZero(string s)  
  128. {  
  129.     int i;  
  130.     for(i=0;i<s.size();i++)  
  131.         if(s[i]!='0') break;  
  132.     return s.substr(i);  
  133. }  
  134. int main()  
  135. {  
  136.      //freopen("in.txt","r",stdin);  
  137.    //  freopen("out.txt","w",stdout);  
  138.     string n;  
  139.     int t;  
  140.     cin>>t;  
  141.     while(t--)  
  142.     {  
  143.         cin>>n;  
  144.         n=DeletePreZero(n);  
  145.         cout<<BigInterSqrt(n)<<endl;  
  146.         //cout<<BigInterSqrt(n).size()<<endl;  
  147.     }  
  148.     return 0;  
  149. } 


最后

以上就是腼腆硬币为你收集整理的ACM-高精度模板(综合篇)的全部内容，希望文章能够帮你解决ACM-高精度模板(综合篇)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(37)

相关文章

将十进制转化为八进制的算法_十进制系统转换为八进制系统
将十进制转化为八进制的算法_十进制系统转换为八进制系统
进制之间的转换
进制之间的转换
读书笔记_算法第四版（一）
读书笔记_算法第四版（一）
【图像分割】利用粒子群算法与遗传算法实现图像的自适应多阈值的快速分割前言一、自适应多阈值分割二、代码部分（以粒子群算法与遗传算法优化自适应双阈值分割为例）三、总结
【图像分割】利用粒子群算法与遗传算法实现图像的自适应多阈值的快速分割前言一、自适应多阈值分割二、代码部分（以粒子群算法与遗传算法优化自适应双阈值分割为例）三、总结
ACM-高精度模板(综合篇)
ACM-高精度模板(综合篇)
Java_数组之进制转换
Java_数组之进制转换
蓝桥杯——十六进制转八进制0.前言1.解题过程2.总结
蓝桥杯——十六进制转八进制0.前言1.解题过程2.总结
java基础学习记录之利用数组进行进制转换的学习与练习五
java基础学习记录之利用数组进行进制转换的学习与练习五

评论列表共有 0 条评论

立即
投稿
返回
顶部