高精度模板

  1 //作者：小黑AWM+MashPlant
  2 //注：可以直接把BigInt和一样用cin cout都行，就是高精乘为了速度才用了FFT降低了精度，有需要可以自行更改。
  3 #include <cstdio>
  4 #include <iostream>
  5 #include <cmath>
  6 #include <string>
  7 #include <cstring>
  8 #include <vector>
  9 #include <algorithm>
 10 using namespace std;
 11 const double PI = acos(-1.0);
 12 struct Complex{
 13     double x,y;
 14     Complex(double _x = 0.0,double _y = 0.0){
 15         x = _x;
 16         y = _y;
 17     }
 18     Complex operator-(const Complex &b)const{
 19         return Complex(x - b.x,y - b.y);
 20     }
 21     Complex operator+(const Complex &b)const{
 22         return Complex(x + b.x,y + b.y);
 23     }
 24     Complex operator*(const Complex &b)const{
 25         return Complex(x*b.x - y*b.y,x*b.y + y*b.x);
 26     }
 27 };
 28 void change(Complex y[],int len){
 29     int i,j,k;
 30     for(int i = 1,j = len/2;i<len-1;i++){
 31         if(i < j)    swap(y[i],y[j]);
 32         k = len/2;
 33         while(j >= k){
 34             j = j - k;
 35             k = k/2;
 36         }
 37         if(j < k)    j+=k;
 38     }
 39 }
 40 void fft(Complex y[],int len,int on){
 41     change(y,len);
 42     for(int h = 2;h <= len;h<<=1){
 43         Complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
 44         for(int j = 0;j < len;j += h){
 45             Complex w(1,0);
 46             for(int k = j;k < j + h/2;k++){
 47                 Complex u = y[k];
 48                 Complex t = w*y[k + h/2];
 49                 y[k] = u + t;
 50                 y[k + h/2] = u - t;
 51                 w = w*wn;
 52             }
 53         }
 54     }
 55     if(on == -1){
 56         for(int i = 0;i < len;i++){
 57             y[i].x /= len;
 58         }
 59     }
 60 }
 61 class BigInt
 62 {
 63 #define Value(x, nega) ((nega) ? -(x) : (x))
 64 #define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
 65     static int absComp(const BigInt &lhs, const BigInt &rhs)
 66     {
 67         if (lhs.size() != rhs.size())
 68             return lhs.size() < rhs.size() ? -1 : 1;
 69         for (int i = lhs.size() - 1; i >= 0; --i)
 70             if (lhs[i] != rhs[i])
 71                 return lhs[i] < rhs[i] ? -1 : 1;
 72         return 0;
 73     }
 74     using Long = long long;
 75     const static int Exp = 9;
 76     const static Long Mod = 1000000000;
 77     mutable std::vector<Long> val;
 78     mutable bool nega = false;
 79     void trim() const
 80     {
 81         while (val.size() && val.back() == 0)
 82             val.pop_back();
 83         if (val.empty())
 84             nega = false;
 85     }
 86     int size() const { return val.size(); }
 87     Long &operator[](int index) const { return val[index]; }
 88     Long &back() const { return val.back(); }
 89     BigInt(int size, bool nega) : val(size), nega(nega) {}
 90     BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}
 91 
 92 public:
 93     friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
 94     {
 95         if (n.size())
 96         {
 97             if (n.nega)
 98                 putchar('-');
 99             for (int i = n.size() - 1; i >= 0; --i)
100             {
101                 if (i == n.size() - 1)
102                     printf("%lld", n[i]);
103                 else
104                     printf("%0*lld", n.Exp, n[i]);
105             }
106         }
107         else
108             putchar('0');
109         return os;
110     }
111     friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
112     {
113         BigInt ret(lhs);
114         return ret += rhs;
115     }
116     friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
117     {
118         BigInt ret(lhs);
119         return ret -= rhs;
120     }
121     BigInt(Long x = 0)
122     {
123         if (x < 0)
124             x = -x, nega = true;
125         while (x >= Mod)
126             val.push_back(x % Mod), x /= Mod;
127         if (x)
128             val.push_back(x);
129     }
130     BigInt(const char *s)
131     {
132         int bound = 0, pos;
133         if (s[0] == '-')
134             nega = true, bound = 1;
135         Long cur = 0, pow = 1;
136         for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
137             for (int i = pos; i > pos - Exp; --i)
138                 cur += (s[i] - '0') * pow, pow *= 10;
139         for (cur = 0, pow = 1; pos >= bound; --pos)
140             cur += (s[pos] - '0') * pow, pow *= 10;
141         if (cur)
142             val.push_back(cur);
143     }
144     BigInt &operator=(const char *s){
145         BigInt n(s);
146         *this = n;
147         return n;
148     }
149     BigInt &operator=(const Long x){
150         BigInt n(x);
151         *this = n;
152         return n;
153     }
154     friend std::istream &operator>>(std::istream &is, BigInt &n){
155         string s;
156         is >> s;
157         n=(char*)s.data();
158         return is;
159     }
160     BigInt &operator+=(const BigInt &rhs)
161     {
162         const int cap = std::max(size(), rhs.size()) + 1;
163         val.resize(cap);
164         int carry = 0;
165         for (int i = 0; i < cap - 1; ++i)
166         {
167             val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
168             if (val[i] >= Mod)
169                 val[i] -= Mod, carry = 1;
170             else if (val[i] < 0)
171                 val[i] += Mod, carry = -1;
172         }
173         if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
174         {
175             nega = true, val.pop_back();
176             bool tailZero = true;
177             for (int i = 0; i < cap - 1; ++i)
178             {
179                 if (tailZero && val[i])
180                     val[i] = Mod - val[i], tailZero = false;
181                 else
182                     val[i] = Mod - 1 - val[i];
183             }
184         }
185         trim();
186         return *this;
187     }
188     friend BigInt operator-(const BigInt &rhs)
189     {
190         BigInt ret(rhs);
191         ret.nega ^= 1;
192         return ret;
193     }
194     BigInt &operator-=(const BigInt &rhs)
195     {
196         rhs.nega ^= 1;
197         *this += rhs;
198         rhs.nega ^= 1;
199         return *this;
200     }
201     friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
202     {
203         int len=1;
204         BigInt ll=lhs,rr=rhs;
205         ll.nega = lhs.nega ^ rhs.nega;
206         while(len<2*lhs.size()||len<2*rhs.size())len<<=1;
207         ll.val.resize(len),rr.val.resize(len);
208         Complex x1[len],x2[len];
209         for(int i=0;i<len;i++){
210             Complex nx(ll[i],0.0),ny(rr[i],0.0);
211             x1[i]=nx;
212             x2[i]=ny;
213         }
214         fft(x1,len,1);
215         fft(x2,len,1);
216         for(int i = 0 ; i < len; i++)
217             x1[i] = x1[i] * x2[i];
218         fft( x1 , len , -1 );
219         for(int i = 0 ; i < len; i++)
220             ll[i] = int( x1[i].x + 0.5 );
221         for(int i = 0 ; i < len; i++){
222             ll[i+1]+=ll[i]/Mod;
223             ll[i]%=Mod;
224         }
225         ll.trim();
226         return ll;
227     }
228     friend BigInt operator*(const BigInt &lhs, const Long &x){
229         BigInt ret=lhs;
230         bool negat = ( x < 0 );
231         Long xx = (negat) ? -x : x;
232         ret.nega ^= negat;
233         ret.val.push_back(0);
234         ret.val.push_back(0);
235         for(int i = 0; i < ret.size(); i++)
236             ret[i]*=xx;
237         for(int i = 0; i < ret.size(); i++){
238             ret[i+1]+=ret[i]/Mod;
239             ret[i] %= Mod;
240         }
241         ret.trim();
242         return ret;
243     }
244     BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
245     BigInt &operator*=(const Long &x) { return *this = *this * x; }
246     friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
247     {
248         static std::vector<BigInt> powTwo{BigInt(1)};
249         static std::vector<BigInt> estimate;
250         estimate.clear();
251         if (absComp(lhs, rhs) < 0)
252             return BigInt();
253         BigInt cur = rhs;
254         int cmp;
255         while ((cmp = absComp(cur, lhs)) <= 0)
256         {
257             estimate.push_back(cur), cur += cur;
258             if (estimate.size() >= powTwo.size())
259                 powTwo.push_back(powTwo.back() + powTwo.back());
260         }
261         if (cmp == 0)
262             return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
263         BigInt ret = powTwo[estimate.size() - 1];
264         cur = estimate[estimate.size() - 1];
265         for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
266             if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
267                 cur += estimate[i], ret += powTwo[i];
268         ret.nega = lhs.nega ^ rhs.nega;
269         return ret;
270     }
271     friend BigInt operator/(const BigInt &num,const Long &x){
272         bool negat = ( x < 0 );
273         Long xx = (negat) ? -x : x;
274         BigInt ret;
275         Long k = 0;
276         ret.val.resize( num.size() );
277         ret.nega = (num.nega ^ negat);
278         for(int i = num.size() - 1 ;i >= 0; i--){
279             ret[i] = ( k * Mod + num[i]) / xx;
280             k = ( k * Mod + num[i]) % xx;
281         }
282         ret.trim();
283         return ret;
284     }
285     bool operator==(const BigInt &rhs) const
286     {
287         return nega == rhs.nega && val == rhs.val;
288     }
289     bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
290     bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
291     bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
292     bool operator<=(const BigInt &rhs) const
293     {
294         if (nega && !rhs.nega)
295             return true;
296         if (!nega && rhs.nega)
297             return false;
298         int cmp = absComp(*this, rhs);
299         return nega ? cmp >= 0 : cmp <= 0;
300     }
301     bool operator<(const BigInt &rhs) const
302     {
303         if (nega && !rhs.nega)
304             return true;
305         if (!nega && rhs.nega)
306             return false;
307         return (absComp(*this, rhs) < 0) ^ nega;
308     }
309     void swap(const BigInt &rhs) const
310     {
311         std::swap(val, rhs.val);
312         std::swap(nega, rhs.nega);
313     }
314 };
315 BigInt ba,bb;
316 int main(){
317     cin>>ba>>bb;
318     cout << ba + bb << '
';//和
319     cout << ba - bb << '
';//差
320     cout << ba * bb << '
';//积
321     BigInt d;
322     cout << (d = ba / bb) << '
';//商
323     cout << ba - d * bb << '
';//余
324     return 0;
325 }
View Code