[OI

1.高精度加法

复杂度O(n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define DEBUG(x) cerr << #x << "=" << x << endl
 8 const int L = 110; 
 9 
10 string a, b;
11 
12 string add(string a, string b)//只限两个非负整数相加 
13 {
14     string ans;
15     int na[L] = {0};
16     int nb[L] = {0};
17     int la = a.size();
18     int lb = b.size();
19     for (int i = 0; i < la; i++) 
20         na[la - 1 - i] = a[i] - '0';
21     for (int i = 0; i < lb; i++) 
22         nb[lb - 1 - i] = b[i] - '0';
23     int lmax = la > lb ? la : lb;
24     for (int i = 0; i < lmax; i++) 
25     {
26         na[i] += nb[i];
27         na[i + 1] += na[i] / 10;
28         na[i] %= 10;
29     } 
30     if (na[lmax]) lmax++;
31     for (int i = lmax - 1; i >= 0; i--) 
32         ans += na[i] + '0';
33     return ans;
34 }
35 
36 int main()
37 {
38     ios::sync_with_stdio(false);
39     cin.tie(0);
40     while (cin >> a >> b) 
41         cout << add(a, b) << endl;
42     return 0;
43 }

2.高精度减法

复杂度O(n)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring> 
  5 
  6 using namespace std;
  7 //#define DEBUG(x) cerr << #x << "=" << x << endl
  8 typedef unsigned char BYTE;
  9 
 10 BYTE a[10005] = {0};
 11 BYTE b[10005] = {0};
 12 BYTE *pa = 0, *pb = 0;
 13 int la, lb;
 14 int sign;
 15 
 16 int main()
 17 {
 18     scanf("%s", a);
 19     scanf("%s", b);
 20     la = strlen((char*)a);
 21     lb = strlen((char*)b);
 22     int i;
 23     for (int i = 0; i < la; i++)
 24     {
 25         a[i] -= '0';
 26     }
 27     for (int i = 0; i < lb; i++)
 28     {
 29         b[i] -= '0';
 30     }
 31     if (la > lb)
 32     {
 33         sign = 1;
 34     }
 35     else if (la < lb)
 36     {
 37         sign = 0;
 38     }
 39     else 
 40     {
 41         sign = -1;
 42         int BCT;
 43         for (BCT = 0; BCT < la; BCT++)
 44         {
 45             if (a[BCT] > b[BCT])
 46             {
 47                 sign = 1;
 48                 break;
 49             }
 50             if (a[BCT] < b[BCT])
 51             {
 52                 sign = 0;
 53                 break;
 54             }
 55         }
 56         if (sign == -1)
 57         {
 58             printf("0");
 59             return 0;
 60         }
 61     }
 62     if (sign == 1)
 63     {
 64         pa = a;
 65         pb = b;
 66     }
 67     else 
 68     {
 69         pa = b;
 70         pb = a;
 71         int buf;
 72         buf = la;
 73         la = lb;
 74         lb = buf;
 75     }
 76     memmove(pb + la - lb, pb, lb);
 77     memset(pb, 0, la - lb);
 78     for (int i = 0; i < la; i++)
 79     {
 80         pb[i] = 9 - pb[i];
 81     }
 82     pb[la - 1]++;
 83     for (int i = la - 1; i >= 0; i--)
 84     {
 85         pa[i] += pb[i];
 86         if (pa[i] >= 10)
 87         {
 88             pa[i] -= 10;
 89             if (i != 0)
 90             {
 91                 pa[i - 1]++;
 92             }
 93         }
 94     }
 95     for (int i = 0; i < la; i++)
 96     {
 97         pa[i] += '0';
 98     }
 99     if (sign == 0)
100     {
101         printf("-");
102     }
103     for (int i = 0; i < la; i++)
104     {
105         if (pa[i] != '0')
106         {
107             printf((char*)pa + i);
108             return 0;
109         }
110     }
111     return 0;
112 }

3.高精度乘法

复杂度O(n*n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 const int L = 110;
 9 
10 string a, b;
11 
12 string mul(string a, string b)
13 {
14     string s;
15     int na[L];
16     int nb[L];
17     int nc[L];
18     int La = a.size();
19     int Lb = b.size();
20     fill(na, na + L, 0);
21     fill(nb, nb + L, 0);
22     fill(nc, nc + L, 0);
23     for (int i = La - 1; i >= 0; i--)
24         na[La - i] = a[i] - '0';
25     for (int i = Lb - 1; i >= 0; i--)
26         nb[Lb - i] = b[i] - '0';
27     for (int i = 1; i <= La; i++)
28     {
29         for (int j = 1; j <= Lb; j++)
30         {
31             nc[i + j - 1] += na[i] * nb[j];
32         }
33     }
34     for (int i = 1; i <= La + Lb; i++)
35     {
36         nc[i + 1] += nc[i] / 10;
37         nc[i] %= 10;
38     }
39     if (nc[La + Lb]) 
40        s += nc[La + Lb] + '0';
41     for (int i = La + Lb - 1; i >= 1; i--)
42         s += nc[i] + '0';
43     return s;  
44 }
45 
46 int main()
47 {
48     while (cin >> a >> b) 
49         cout << mul(a, b) << endl;
50     return 0;
51 }

4.高精度乘法FFT优化

复杂度O(nlogn)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 //#define DEBUG(x) cerr << #x << "=" << x << endl
  9 #define L(x) (1 << (x))
 10 const double PI = acos(-1.0);
 11 const int maxn = 133015;
 12 
 13 double ax[maxn], ay[maxn], bx[maxn], by[maxn];
 14 char sa[maxn / 2], sb[maxn / 2];
 15 int sum[maxn];
 16 int x1[maxn], x2[maxn];
 17 string a, b;
 18 
 19 int max(int a, int b)
 20 {
 21     return a > b ? a : b;
 22 }
 23 
 24 int revv(int x, int bits)
 25 {
 26     int ret = 0;
 27     for (int i = 0; i < bits; i++)
 28     {
 29         ret <<= 1;
 30         ret |= x & 1;
 31         x >>= 1;
 32     }
 33     return ret;
 34 }
 35 
 36 void fft(double *a, double *b, int n, bool rev)
 37 {
 38     int bits = 0;
 39     while (1 << bits < n) 
 40         ++bits;
 41     for (int i = 0; i < n; i++)
 42     {
 43         int j = revv(i, bits);
 44         if (i < j)
 45         {
 46             swap(a[i], a[j]);
 47             swap(b[i], b[j]);
 48         }
 49     }
 50     for (int len = 2; len <= n; len <<= 1)
 51     {
 52         int half = len >> 1;
 53         double wmx = cos(2 * PI / len);
 54         double wmy = sin(2 * PI / len);
 55         if (rev)
 56             wmy = -wmy;
 57         for (int i = 0; i < n; i += len)
 58         {
 59             double wx = 1;
 60             double wy = 0;
 61             for (int j = 0; j < half; j++)
 62             {
 63                 double cx = a[i + j];
 64                 double cy = b[i + j];
 65                 double dx = a[i + j + half];
 66                 double dy = b[i + j + half];
 67                 double ex = dx * wx - dy * wy;
 68                 double ey = dx * wy + dy * wx;
 69                 a[i + j] = cx + ex;
 70                 b[i + j] = cy + ey;
 71                 a[i + j + half] = cx - ex;
 72                 b[i + j + half] = cy - ey;
 73                 double wnx = wx * wmx - wy * wmy;
 74                 double wny = wx * wmy + wy * wmx;
 75                 wx = wnx;
 76                 wy = wny;
 77             }
 78         }
 79     }
 80     if (rev)
 81     {
 82         for (int i = 0; i < n; i++)
 83         {
 84             a[i] /= n;
 85             b[i] /= n;
 86         }
 87     }
 88 }
 89 
 90 int solve(int a[], int na, int b[], int nb, int ans[])
 91 {
 92     int len = max(na, nb);
 93     int ln;
 94     for (int ln = 0; L(ln) < len; ++ln)
 95         len = L(++ln);
 96     for (int i = 0; i < len; ++i)
 97     {
 98         if (i >= na)
 99         {
100             ax[i] = 0;                                                            
101             ay[i] = 0;
102         }             
103         else
104         {
105             ax[i] = a[i];
106             ay[i] = 0;
107         }                         
108     }
109     fft(ax, ay, len, 0);
110     for (int i = 0; i < len; ++i)
111     {
112         if (i >= nb)
113         {
114             bx[i] = 0;
115             by[i] = 0;
116         }
117         else 
118         {
119             bx[i] = b[i];
120             by[i] = 0;
121         }
122     }
123     fft(bx, by, len, 0);
124     for (int i = 0; i < len; ++i)
125     {
126         double cx = ax[i] * bx[i] - ay[i] * by[i];
127         double cy = ax[i] * by[i] + ay[i] * bx[i];
128         ax[i] = cx;
129         ay[i] = cy;
130     }
131     fft(ax, ay, len, 1);
132     for (int i = 0; i < len; ++i)
133         ans[i] = (int)(ax[i] + 0.5);
134     return len;
135 }
136 
137 string mul(string sa, string sb)
138 {
139     int l1, l2, l;
140     int i;
141     string ans;
142     memset(sum, 0, sizeof(sum));
143     l1 = sa.size();
144     l2 = sb.size();
145     for (int i = 0; i < l1; i++)
146         x1[i] = sa[l1 - i - 1] - '0';
147     for (int i = 0; i < l2; i++)
148         x2[i] = sb[l2 - i - 1] - '0';
149     l = solve(x1, l1, x2, l2, sum);
150     for (int i = 0; i < l || sum[i] >= 10; i++)
151     {
152         sum[i + 1] += sum[i] / 10;
153         sum[i] %= 10;
154     }
155     l = i;
156     while (sum[l] <= 0 && l > 0)
157         l--;
158     for (int i = l; i >= 0; i--)
159         ans += sum[i] + '0';
160     return ans;
161 }
162 
163 int main()
164 {
165     ios::sync_with_stdio(false);
166     cin.tie(0);
167     while (cin >> a >> b)
168         cout << mul(a, b) << endl;
169     return 0;
170 }

5.高精度乘单精度乘法

复杂度O(n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 const int L = 1e5 + 7;
 9 
10 int na[L];
11 string a;
12 int b;
13 
14 string mul(string a, int b)
15 {
16     string ans;
17     int La = a.size();
18     fill(na, na + L, 0);
19     for (int i = La - 1; i >= 0; i--)
20     na[La - i - 1] = a[i] - '0';
21     int w = 0;
22     for (int i = 0; i < La; i++)
23     {
24         na[i] = na[i] * b + w;
25         w = na[i] / 10;
26         na[i] = na[i] % 10;
27     }
28     while (w)
29     {
30         na[La++] = w % 10;
31         w /= 10;
32     }
33     La--;
34     while (La >= 0) 
35         ans += na[La--] + '0';
36     return ans;
37 }
38 
39 int main()
40 {
41     ios::sync_with_stdio(false);
42     cin.tie(0);
43     while (cin >> a >> b) 
44         cout << mul(a, b) << endl;
45     return 0;
46 }

6.高精度除法(包括取模)

复杂度O(n*n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 const int L = 110;
 9 
10 string a, b;
11 
12 int sub(int *a, int *b, int La, int Lb)
13 {
14     if (La < Lb) return -1;
15     if (La == Lb)
16     {
17         for (int i = La - 1; i >= 0; i--)
18         {
19             if (a[i] > b[i]) break;
20             else if (a[i] < b[i]) return -1;
21         }
22     }
23     for (int i = 0; i < La; i++)
24     {
25         a[i] -= b[i];
26         if (a[i] < 0) 
27         {
28             a[i] += 10;
29             a[i + 1]--;
30         }
31     }
32     for (int i = La - 1; i >= 0; i--)
33         if (a[i]) return i + 1;
34     return 0;
35 }
36 
37 string div(string n1, string n2, int nn)
38 {
39     string s, v;
40     int a[L], b[L], r[L];
41     int La = n1.size(), Lb = n2.size();
42     int i, tp = La;
43     fill(a, a + L, 0);
44     fill(b, b + L, 0);
45     fill(r, r + L, 0);
46     for (int i = La - 1; i >= 0; i--) a[La - i - 1] = n1[i] - '0';
47     for (int i = Lb - 1; i >= 0; i--) b[Lb - i - 1] = n2[i] - '0';
48     if (La < Lb || (La == Lb && n1 < n2))
49     {
50         return n1;
51     }
52     int t = La - Lb;
53     for (int i = La - 1;i >= 0; i--)
54         if (i >= t) b[i] = b[i - t];
55         else b[i] = 0;
56     Lb = La;
57     for (int j = 0; j <= t; j++)
58     {
59         int temp;
60         while ((temp = sub(a, b + j, La, Lb - j)) >= 0)
61         {
62             La = temp;
63             r[t - j]++;
64         }
65     }
66     for (int i = 0; i < L - 10; i++)
67     {
68         r[i + 1] += r[i] / 10;
69         r[i] %= 10;
70     }
71     while (!r[i]) i--;
72     while (i >= 0) s += r[i--] + '0';
73     i = tp;
74     while (!a[i]) i--;
75     while (i >= 0) v += a[i--] + '0';
76     if (v.empty()) v = "0";
77     if (nn == 1) return s;
78     if (nn == 2) return v; 
79 }
80 
81 int main()
82 {
83     ios::sync_with_stdio(false);
84     cin.tie(0);
85     while (cin >> a >> b) 
86         cout << div(a, b, 1) << endl;
87     return 0;
88 }

7.高精度除单精度除法

复杂度O(n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 
 9 string a;
10 int b;
11 
12 string div(string a, int b)
13 {
14     string r, ans;
15     int d = 0;
16     if (a == "0") return a;
17     for (int i = 0; i < a.size(); i++)
18     {
19         r += (d * 10 + a[i] - '0') / b + '0';
20         d = (d * 10  + (a[i] - '0')) % b;
21     }
22     int p = 0;
23     for (int i = 0; i < r.size(); i++)
24         if (r[i] != '0')
25         {
26             p = i;
27             break;
28         }
29     return r.substr(p);
30 }
31 
32 int main()
33 {
34     ios::sync_with_stdio(false);
35     cin.tie(0);
36     while (cin >> a >> b)
37     {
38         cout << div(a, b) << endl;
39     }
40     return 0;
41 }

8.高精度对单精度取模

复杂度O(n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 
 9 string a;
10 int b;
11 
12 int mod(string a, int b)
13 {
14     int d = 0;
15     for (int i = 0; i < a.size(); i++) 
16         d = (d * 10 + (a[i] - '0')) % b;
17     return d;
18 }
19 
20 int main()
21 {
22     ios::sync_with_stdio(false);
23     cin.tie(0);
24     while (cin >> a >> b)
25     {
26         cout << mod(a, b) << endl;
27     }
28     return 0;
29 }

9.高精度阶乘

复杂度O(n*n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl
 8 const int L = 1e5 + 7;
 9 
10 int a[L];
11 int n;
12 
13 string fac(int n)
14 {
15     string ans;
16     if (n == 0) return "1";
17     fill(a, a + L, 0);
18     int s = 0;
19     int m = n;
20     while (n)
21     {
22         a[++s] = m % 10;
23         m /= 10;
24     }
25     for (int i = n - 1; i >= 2; i--)
26     {
27         int w = 0;
28         for (int j = 1; j <= s; j++)
29         {
30             a[j] = a[j] * i + w;
31             w = a[j] / 10;
32             a[j] = a[j] % 10;
33         }
34     }
35     while (!a[s]) s--;
36     while (s >= 1) ans += a[s--] + '0';;
37     return ans;
38 }
39 
40 int main()
41 {
42     ios::sync_with_stdio(false);
43     cin.tie(0);
44     while (cin >> n)
45         cout << fac(n) << endl;
46     return 0;
47 }

10.高精度幂

复杂度O(nlognlogm)

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 //#define DEBUG(x) cerr << #x << "=" << x << endl
  9 #define L(x) (1 << (x))
 10 const double PI = acos(-1.0);
 11 const int maxn = 122515;
 12 
 13 double ax[maxn], ay[maxn], bx[maxn], by[maxn];
 14 char sa[maxn / 2], sb[maxn / 2];
 15 int sum[maxn];
 16 int b;
 17 int x1[maxn], x2[maxn];
 18 string a;
 19 
 20 int revv(int x, int bits)
 21 {
 22     int ret = 0;
 23     for (int i = 0; i < bits; i++)
 24     {
 25         ret <<= 1;
 26         ret |= x & 1;
 27         x >>= 1;
 28     }
 29     return ret;
 30 }
 31 
 32 void fft(double *a, double *b, int n, bool rev)
 33 {
 34     int bits = 0;
 35     while (1 << bits < n) ++bits;
 36     for (int i = 0; i < n; i++)
 37     {
 38         int j = revv(i, bits);
 39         if (i < j)
 40         {
 41             swap(a[i], a[j]);
 42             swap(b[i], b[j]);
 43         }
 44     }
 45     for (int len = 2; len <= n; len <<= 1)
 46     {
 47         int half = len >> 1;
 48         double wmx = cos(PI * 2 / len);
 49         double wmy = sin(PI * 2 / len);
 50         if (rev) wmy = -wmy;
 51         for (int i = 0; i < n; i += len)
 52         {
 53             double wx = 1;
 54             double wy = 0;
 55             for (int j = 0; j < half; j++)
 56             {
 57                 double cx = a[i + j];
 58                 double cy = b[i + j];
 59                 double dx = a[i + j + half];
 60                 double dy = a[i + j + half];
 61                 double ex = dx * wx - dy * wy;
 62                 double ey = dx * wy + dy * wx;
 63                 a[i + j] = cx + ex;
 64                 b[i + j] = cy + ey;
 65                 a[i + j + half] = cx - ex;
 66                 a[i + j + half] = cy - ey;
 67                 double wnx = wx * wmx - wy * wmy;
 68                 double wny = wx * wmy + wy * wmx;
 69                 wx = wnx;
 70                 wy = wny;
 71             }
 72         }
 73     }
 74     if (rev)
 75     {
 76         for (int i = 0; i < n; i++)
 77         {
 78             a[i] /= n;
 79             b[i] /= n; 
 80         }
 81     }
 82 }
 83 
 84 int solve(int a[], int na, int b[], int nb, int ans[])  
 85 {  
 86     int len = max(na, nb);
 87     int ln;  
 88     for (ln = 0; L(ln) < len; ++ln);  
 89         len = L(++ln);  
 90     for (int i = 0; i < len; ++i)  
 91     {  
 92         if (i >= na) 
 93         {
 94             ax[i] = 0;
 95             ay[i] = 0;
 96         }  
 97         else
 98         {
 99             ax[i] = a[i];
100             ay[i] = 0;
101         }  
102     }  
103     fft(ax, ay, len, 0);  
104     for (int i = 0; i < len; ++i)  
105     {  
106         if (i >= nb)
107         {
108             bx[i] = 0;
109             by[i] = 0;
110         }  
111         else 
112         {
113             bx[i] = b[i];
114             by[i] = 0;
115         }  
116     }  
117     fft(bx, by, len, 0);  
118     for (int i = 0; i < len; ++i)  
119     {  
120         double cx = ax[i] * bx[i] - ay[i] * by[i];  
121         double cy = ax[i] * by[i] + ay[i] * bx[i];  
122         ax[i] = cx;
123         ay[i] = cy;  
124     }  
125     fft(ax, ay, len, 1);  
126     for (int i = 0; i < len; ++i)  
127         ans[i] = (int)(ax[i] + 0.5);  
128     return len;  
129 }  
130 
131 string mul(string sa, string sb)  
132 {  
133     int l1, l2, l;  
134     int i;  
135     string ans;  
136     memset(sum, 0, sizeof(sum));  
137     l1 = sa.size();  
138     l2 = sb.size();  
139     for (i = 0; i < l1; i++)  
140         x1[i] = sa[l1 - i - 1] - '0';  
141     for (i = 0; i < l2; i++)  
142         x2[i] = sb[l2 - i - 1] - '0';  
143     l = solve(x1, l1, x2, l2, sum);  
144     for (i = 0; i < l || sum[i] >= 10; i++)   
145     {  
146         sum[i + 1] += sum[i] / 10;  
147         sum[i] %= 10;  
148     }  
149     l = i;  
150     while(sum[l] <= 0 && l>0)    
151         l--; 
152     for(i = l; i >= 0; i--)    
153         ans += sum[i] + '0';   
154     return ans;  
155 }  
156 
157 string Pow(string a, int n)  
158 {  
159     if(n == 1) return a;  
160     if(n & 1) return mul(Pow(a, n - 1), a);  
161     string ans = Pow(a, n / 2);  
162     return mul(ans, ans);  
163 }  
164 
165 int main()  
166 {  
167     ios::sync_with_stdio(false);
168     cin.tie(0);    
169     while (cin >> a >> b) 
170         cout << Pow(a, b) << endl;  
171     return 0;  
172 }

11.高精度GCD

复杂度玄学

  1 #include <iostream>
  2 #include <cstdio>  
  3 #include <cstring>  
  4 #include <algorithm>
  5   
  6 using namespace std;  
  7 //#define DEBUG(x) cerr << #x << "=" << x << endl
  8 const int L = 110;
  9 
 10 string a, b;
 11   
 12 string add(string a, string b)  
 13 {  
 14     string ans;  
 15     int na[L] = {0};
 16     int nb[L] = {0};  
 17     int la = a.size();
 18     int lb = b.size();  
 19     for (int i = 0; i < la; i++) 
 20         na[la - 1 - i] = a[i] - '0';  
 21     for (int i = 0; i < lb; i++)
 22         nb[lb - 1 - i] = b[i] - '0';  
 23     int lmax = la > lb ? la : lb;  
 24     for (int i = 0; i < lmax; i++) 
 25     {
 26         na[i] += nb[i];
 27         na[i + 1] += na[i] / 10;
 28         na[i] %= 10;
 29     }  
 30     if (na[lmax]) 
 31         lmax++;  
 32     for (int i = lmax - 1; i >= 0; i--) 
 33         ans += na[i] + '0';  
 34     return ans;  
 35 }  
 36 
 37 string mul(string a, string b)  
 38 {  
 39     string s;  
 40     int na[L];
 41     int nb[L];
 42     int nc[L];
 43     int La = a.size();
 44     int Lb = b.size();  
 45     fill(na, na + L, 0);
 46     fill(nb, nb + L, 0);
 47     fill(nc, nc + L, 0);  
 48     for (int i = La - 1; i >= 0; i--)
 49         na[La - i] = a[i] - '0';  
 50     for (int i = Lb - 1; i >= 0; i--) 
 51         nb[Lb - i] = b[i] - '0';  
 52     for (int i = 1; i <= La; i++)  
 53         for (int j = 1; j <= Lb; j++)  
 54             nc[i + j - 1] += na[i] * nb[j];  
 55     for (int i = 1; i <= La + Lb; i++)  
 56     {
 57         nc[i + 1] += nc[i] / 10;
 58         nc[i] %= 10;
 59     } 
 60     if (nc[La + Lb]) 
 61         s += nc[La + Lb] + '0';  
 62     for (int i = La + Lb - 1; i >= 1; i--)  
 63         s += nc[i] + '0'; 
 64     return s;  
 65 }  
 66 
 67 int sub(int *a, int *b, int La, int Lb)  
 68 {  
 69     if (La < Lb) return -1;  
 70     if (La == Lb)  
 71     {  
 72         for (int i = La - 1; i >= 0; i--)  
 73             if (a[i] > b[i]) break;  
 74                 else if(a[i] < b[i]) return -1; 
 75     }  
 76     for (int i = 0; i < La; i++) 
 77     {  
 78         a[i] -= b[i];  
 79         if (a[i] < 0) 
 80         {
 81             a[i] += 10;
 82             a[i + 1]--;
 83         }  
 84     }  
 85     for (int i = La - 1; i >= 0; i--)  
 86         if (a[i]) return i + 1;  
 87     return 0;
 88 }  
 89 
 90 string div(string n1, string n2, int nn)  
 91 {  
 92     string s;
 93     string v;
 94     int a[L];
 95     int b[L];
 96     int r[L];
 97     int La = n1.size();
 98     int Lb = n2.size();
 99     int i, tp = La;  
100     fill(a, a + L, 0);
101     fill(b, b + L, 0);
102     fill(r, r + L, 0); 
103     for (i = La - 1; i >= 0; i--) 
104         a[La - 1 - i] = n1[i] - '0';  
105     for (i = Lb - 1; i >= 0; i--)
106         b[Lb - 1 - i] = n2[i] - '0';  
107      if (La < Lb || (La == Lb && n1 < n2)) 
108      {  
109             return n1;
110      }
111      int t = La - Lb;
112      for (int i = La - 1; i >= 0; i--) 
113          if (i >= t) 
114              b[i] = b[i - t];  
115              else b[i] = 0;  
116      Lb = La;  
117      for (int j = 0; j <= t; j++)  
118      {  
119          int temp;  
120          while ((temp = sub(a, b + j, La, Lb - j)) >= 0)  
121          {  
122              La = temp;  
123              r[t - j]++;  
124          }  
125      }  
126      for (i = 0; i < L - 10; i++) 
127      {
128           r[i + 1] += r[i] / 10;
129          r[i] %= 10;
130      } 
131      while (!r[i]) i--;  
132      while (i >= 0) 
133           s += r[i--] + '0';  
134      i = tp;  
135      while (!a[i]) i--;  
136      while (i >= 0) 
137           v += a[i--] + '0';  
138      if (v.empty()) v = "0";  
139      if(nn == 1) return s;  
140      if(nn == 2) return v;  
141 }  
142 
143 bool judge(string s)  
144 {  
145     for (int i = 0; i < s.size(); i++)  
146         if (s[i] != '0') 
147             return false;  
148     return true;  
149 }  
150 
151 string gcd(string a, string b)  
152 {  
153     string t;  
154     while (!judge(b)) 
155     {  
156         t = a;  
157         a = b;  
158         b = div(t, b, 2); 
159     }  
160     return a;  
161 }  
162 
163 int main()  
164 {  
165     ios::sync_with_stdio(false); 
166     cin.tie(0);   
167     while (cin>>a>>b) 
168         cout<<gcd(a,b)<<endl;  
169     return 0;  
170 }

12.高精度进制转换

复杂度O(n*n)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>  
 4 #include <algorithm>
 5   
 6 using namespace std; 
 7 //#define DEBUG(x) cerr << #x << "=" << x << endl  
 8 
 9 string s;
10 
11 bool judge(string s)  
12 {  
13     for (int i = 0; i < s.size(); i++)  
14         if (s[i] != '0') 
15             return 1;  
16     return 0;  
17 }  
18 
19 string solve(string s, int n, int m) 
20 {  
21     string r, ans;  
22     int d = 0;  
23     if (!judge(s)) return "0";
24     while (judge(s)) 
25     {  
26         for (int i = 0; i < s.size(); i++)  
27         {  
28             r += (d * n + s[i] - '0') / m + '0'; 
29             d = (d * n + (s[i] - '0')) % m; 
30         }  
31        s = r;
32        r = ""; 
33        ans += d + '0'; 
34        d = 0;
35     }  
36     reverse(ans.begin(), ans.end());      
37     return ans;  
38 }  
39 
40 int main()  
41 {  
42     ios::sync_with_stdio(false);
43     cin.tie(0);  
44     while(cin>>s)  
45     {  
46         cout << solve(s, 10, 7) << endl;  
47     }  
48     return 0;  
49 }

13.高精度平方根

复杂度O(n*n*n)

  1 #include <iostream>  
  2 #include <cstring>  
  3 #include <cstdio>  
  4 #include <algorithm> 
  5  
  6 using namespace std;  
  7 //#define DEBUG(x) cerr << #x << "=" << x << endl
  8 const int L = 2018;  
  9 
 10 string n;  
 11 int t; 
 12 
 13 string add(string a, string b)//只限两个非负整数相加  
 14 {  
 15     string ans;  
 16     int na[L] = {0};
 17     int nb[L] = {0};  
 18     int la = a.size();
 19     int lb = b.size();  
 20     for (int i = 0; i < la; i++) 
 21         na[la - 1 - i] = a[i] - '0';  
 22     for (int i = 0; i <lb; i++) 
 23         nb[lb - 1 - i] = b[i] - '0';  
 24     int lmax = la > lb ? la : lb;  
 25     for (int i = 0; i < lmax; i++) 
 26     {
 27         na[i] += nb[i];
 28         na[i + 1] += na[i] / 10;
 29         na[i] %= 10;
 30     }  
 31     if (na[lmax]) lmax++;  
 32     for (int i = lmax - 1; i >= 0; i--) 
 33         ans += na[i] + '0';  
 34     return ans;  
 35 }  
 36 
 37 string sub(string a, string b)//只限大的非负整数减小的非负整数  
 38 {  
 39     string ans;  
 40     int na[L] = {0};
 41     int nb[L] = {0};  
 42     int la = a.size();
 43     int lb = b.size();  
 44     for (int i = 0; i < la; i++) 
 45         na[la - 1 - i] = a[i] - '0';  
 46     for (int i = 0; i < lb; i++) 
 47         nb[lb - 1 - i] = b[i] - '0';  
 48     int lmax = la > lb ? la : lb;  
 49     for (int i = 0; i < lmax; i++)  
 50     {  
 51         na[i] -= nb[i];  
 52         if (na[i] < 0)
 53         {
 54             na[i] += 10;
 55             na[i + 1]--;
 56         }  
 57     }  
 58     while (!na[--lmax] && lmax > 0) lmax++;  
 59     for (int i = lmax - 1; i >= 0; i--) 
 60         ans += na[i] + '0';  
 61     return ans;  
 62 }  
 63 
 64 string mul(string a, string b)//高精度乘法a,b,均为非负整数  
 65 {  
 66     string s;  
 67     int na[L];
 68     int nb[L];
 69     int nc[L];
 70     int La = a.size();
 71     int Lb = b.size(); 
 72     fill(na, na + L, 0);
 73     fill(nb, nb + L, 0);
 74     fill(nc, nc + L, 0);  
 75     for (int i = La - 1; i >= 0; i--) 
 76         na[La - i] = a[i] - '0';
 77     for (int i = Lb - 1; i >= 0; i--) 
 78         nb[Lb - i] = b[i] - '0';  
 79     for (int i = 1; i <= La; i++)  
 80         for (int j = 1; j <= Lb; j++)  
 81             nc[i + j - 1] += na[i] * nb[j];  
 82     for (int i = 1; i <= La + Lb; i++)  
 83     {
 84         nc[i + 1] += nc[i] / 10;
 85         nc[i] %= 10;
 86     } 
 87     if (nc[La + Lb]) 
 88         s += nc[La + Lb] + '0'; 
 89     for (int i = La + Lb - 1; i >= 1; i--)  
 90         s += nc[i] + '0';
 91     return s;  
 92 }  
 93 
 94 int sub(int *a, int *b, int La, int Lb)  
 95 {  
 96     if (La < Lb) return -1;
 97     if (La == Lb)  
 98     {  
 99         for (int i = La - 1; i >= 0; i--)  
100             if (a[i] > b[i]) break;  
101                 else if (a[i] < b[i]) return -1; 
102     }  
103     for (int i = 0; i < La; i++)
104     {  
105         a[i] -= b[i];  
106         if (a[i] < 0) 
107         {
108             a[i] += 10;
109             a[i + 1]--;
110         }  
111     }  
112     for (int i = La - 1; i >= 0; i--)  
113         if (a[i]) return i + 1;  
114     return 0;
115 }  
116 
117 string div(string n1, string n2, int nn)  
118 {  
119     string s;
120     string v;
121     int a[L];
122     int b[L];
123     int r[L];
124     int La = n1.size();
125     int Lb = n2.size();
126     int i, tp = La;  
127     fill(a, a + L, 0);
128     fill(b, b + L, 0);
129     fill(r, r + L, 0); 
130     for (i = La - 1; i >= 0; i--) 
131         a[La - 1 - i] = n1[i] - '0';  
132     for (i = Lb - 1; i >= 0; i--)
133         b[Lb - 1 - i] = n2[i] - '0';  
134     if (La < Lb || (La == Lb && n1 < n2)) 
135     {  
136            return n1;
137     }
138     int t = La - Lb;
139     for (int i = La - 1; i >= 0; i--) 
140         if (i >= t) 
141             b[i] = b[i - t];  
142         else b[i] = 0;  
143     Lb = La;  
144     for (int j = 0; j <= t; j++)  
145     {  
146        int temp;  
147        while ((temp = sub(a, b + j, La, Lb - j)) >= 0)  
148         {  
149             La = temp;  
150             r[t - j]++;  
151         }  
152     }  
153     for (i = 0; i < L - 10; i++) 
154     {
155          r[i + 1] += r[i] / 10;
156          r[i] %= 10;
157     } 
158     while (!r[i]) i--;  
159     while (i >= 0) 
160          s += r[i--] + '0';  
161     i = tp;  
162     while (!a[i]) i--;  
163     while (i >= 0) 
164          v += a[i--] + '0';  
165     if (v.empty()) v = "0";  
166     if (nn == 1) return s;  
167     if (nn == 2) return v;  
168 }  
169 
170 bool cmp(string a, string b)  
171 {  
172     if (a.size() < b.size()) return 1; 
173     if (a.size() == b.size() && a <= b) return 1;  
174     return 0;  
175 }  
176 
177 string BigInterSqrt(string n)  
178 {  
179     string l = "1";
180     string r = n;
181     string mid;
182     string ans;  
183     while (cmp(l, r))  
184     {  
185         mid = div(add(l, r), "2", 1);  
186         if (cmp(mul(mid, mid), n))
187         {
188             ans = mid;
189             l = add(mid, "1");
190         }  
191         else r = sub(mid, "1");  
192     }  
193     return ans;  
194 }  
195 
196 string DeletePreZero(string s)  
197 {  
198     int i;  
199     for (i = 0; i < s.size(); i++)  
200         if (s[i] != '0') break;  
201     return s.substr(i);  
202 }  
203 
204 int main()  
205 {   
206     ios::sync_with_stdio(false);
207     cin.tie(0);
208     cin >> t;  
209     while (t--)  
210     {  
211         cin >> n;  
212         n = DeletePreZero(n);  
213         cout << BigInterSqrt(n) << endl;    
214     }  
215     return 0;  
216 }