模板高精度

Updated on 11.03 重载小于号的更新
  1 struct Big {
  2     const static int N = 1005;
  3     int a[N];
  4     bool flag;
  5     Big(){ms(a,0),flag = 0;}
  6     Big( ll x ){
  7         ms(a,0),flag = 0;
  8         if(x == 0) return;
  9         flag = (x < 0);
 10         x = max(x,-x);
 11         while(x) a[++a[0]] = x%10,x/=10;
 12         clr0();
 13     }
 14     void read() {
 15         ms(a,0),flag = 0;
 16         char s[N];
 17         scanf("%s",s+1);
 18         a[0] = strlen(s+1);
 19         if(s[1] == '-') a[0]--,flag = 1;
 20         rep(i,1,a[0]) a[i] = s[a[0] - i + flag + 1] - '0';
 21         clr0();
 22     }
 23     void clr0() {
 24         while(a[0] && a[a[0]] == 0) a[0]--;
 25         while(a[0] < 0) a[0]++;
 26         if(a[0] == 0) flag = 0;
 27     }
 28     void print() {
 29         clr0();
 30         if(!a[0]) return void(puts("0"));
 31         if(flag) putchar('-');
 32         per(i,a[0],1) putchar(a[i] + '0');
 33         putchar('
');
 34     }
 35     //clr0 before use
 36     bool operator < (const Big &o) const {
 37         if(o.a[0] == 0) return flag;
 38         if(a[0] == 0) return !o.flag;
 39         if(flag ^ o.flag) return flag;
 40         if(a[0] ^ o.a[0]) return ((a[0] < o.a[0]) ^ flag);
 41         per(i,a[0],1) {
 42             if(a[i] > o.a[i]) return flag;
 43             if(a[i] < o.a[i]) return !flag;
 44         }
 45         return 0;
 46     }
 47     bool operator == (const Big &o) const {
 48         Big r = *this;
 49         return !(r < o || o < r);
 50     }
 51     //保证同号
 52     Big operator + (const Big &o) const {
 53         if(a[0] == 0) return o;
 54         if(o.a[0] == 0) return *this;
 55         if(flag ^ o.flag) {
 56             Big x = *this,y = o;
 57             if(x.flag) {
 58                 x.flag = 0;
 59                 return y - x;
 60             }
 61             else {
 62                 y.flag = 0;
 63                 return x - y;
 64             }
 65         }
 66         Big ans;
 67         ms(ans.a,0);
 68         ans.a[0] = max(a[0],o.a[0]),ans.flag = flag;
 69         rep(i,1,ans.a[0]) {
 70             ans.a[i] += a[i] + o.a[i];
 71             if(i == ans.a[0] && ans.a[i] >= 10) {
 72                 ans.a[0]++;
 73             }
 74             ans.a[i+1] += ans.a[i] / 10;
 75             ans.a[i] %= 10;
 76         }
 77         return ans;
 78     }
 79     //保证同号
 80     Big operator - (const Big &o) const {
 81         Big x = *this;
 82         Big y = o;
 83         if(flag ^ o.flag) {
 84             y.flag ^= 1;
 85             return x + y;
 86         }
 87         Big ans;
 88         ms(ans.a,0);
 89         ans.a[0] = ans.flag = 0;
 90         ans.flag = flag;
 91         x.flag = y.flag = 0;
 92         if(x == y) return ans;
 93         if(x < y) swap(x,y),ans.flag ^= 1;
 94         rep(i,1,x.a[0]) {
 95             if(x.a[i] < y.a[i]) x.a[i] += 10,x.a[i+1]--;
 96             ans.a[i] = x.a[i] - y.a[i];
 97         }
 98         ans.a[0] = x.a[0];
 99         ans.clr0();
100         return ans;
101     }
102     //O(n^2) 高精乘
103     Big operator * (const Big &o) const {
104         if(a[0] == 0) return *this;
105         if(o.a[0] == 0) return o;
106         Big ans;
107         ms(ans.a,0);
108         ans.a[0] = a[0] + o.a[0],ans.flag = o.flag ^ flag;
109         rep(i,1,a[0]) rep(j,1,o.a[0])
110             ans.a[i+j-1] += a[i] * o.a[j];
111         rep(i,1,ans.a[0]) {
112             if(i == ans.a[0] && ans.a[i] >= 10) ans.a[0]++;
113             ans.a[i+1] += ans.a[i] / 10;
114             ans.a[i] %= 10;
115         }
116         return ans;
117     }
118 };
仍然欢迎Hack
> 别忘了总有人在等着你
模板 高精度

模板高精度
