手写压位高精度（N^2)乘法

O(N)加法
没什么出众的地方，只是一次作业，也当练习一下。

#include<bits/stdc++.h>

// by.dayi 23.5.10
// 第一次尝试写压位高精度
// 其实python可太容易了，但是想趁着机会练一下手写

const int maxn = 10086; // 数组长度，高精度最大可以存4*maxn位，可以无限增加，但是乘法是n^2实现的
const int power = 4; //10^4次方，高精度压位，每个位存4位,因为10^8<2^31，但是10^10>2^31
const int base  = 1e4; // 基数

//最大值 最小值
template <typename T> T max(T a,T b){return a>b?a:b;} 
template <typename T> T min(T a,T b){return a<b?a:b;} 

struct big_dec{//高精度
  int a[maxn];//数组长度
  int _len_big_dec;//当前长度
  int f;

  big_dec(){//结构体构造函数，初始化
    memset(a,0,sizeof(a));
    _len_big_dec = 0;
    f = 0;//f=1为负数
  }

  //从字符串读取
  inline void read_from_str(const char *str){
    int len = strlen(str);//数组长度
    int k = 1;//当前的位置
    int w = 1;//当前位的权值
    int end = 0;//结束位置

    //负数
    if(str[0]=='-'){f=1;end=1;}

    for(int i=len-1;i>=end;i--){
      // 12   345678
      // a[2] a[1]
      a[k] += (str[i]-'0')*w;//加位
      w*=10;//权值增加
      if(w==base){//权值到达基数
        w = 1;//权值归1
        k++;//位置增加
      }
    }
    _len_big_dec = k;
  }
  
  bool is_zero() const { //是否是0
    return _len_big_dec == 1 && a[1] == 0;
  }

  big_dec abs() const { //绝对值
    big_dec ans = *this;
    ans.f = 0;
    return ans;
  }

  //stdout标准输出
  inline void print_stdout(){
    if(this->f)printf("-");//负数
    for(int i=_len_big_dec;i>=1;i--){
      if(i==_len_big_dec && a[i]!=0) printf("%d",a[i]);
      else printf("%04d",a[i]);
    }
  }

  //赋值，也是复制
  big_dec operator = (const big_dec &b){
    _len_big_dec = b._len_big_dec;
    f = b.f;
    for(int i=1;i<=_len_big_dec;i++){
      a[i] = b.a[i];
    }
    return *this;
  }

  // 小于号
  bool operator<(const big_dec &b) const {
    if (f != b.f) {return f > b.f;} //0为正数，1为负数，0>1 
    if (_len_big_dec != b._len_big_dec) {//长度
      return f?(_len_big_dec > b._len_big_dec):(_len_big_dec < b._len_big_dec);
    }

    //长度相同，判断每一位
    for (int i=_len_big_dec;i>=1;i--){
      if (a[i]!=b.a[i]) {
        return f?(a[i]>b.a[i]):(a[i]<b.a[i]);
      }
    }
    return false; // 相等
  }

  // 大于号
  bool operator>(const big_dec &b) const {
    return b<*this; // 反向比较即可
  }


  //加法，要命
  big_dec operator + (const big_dec &b){
    big_dec ans;//结果
    if(f==b.f){//同号相加
      ans.f=b.f;
      int len=max(_len_big_dec,b._len_big_dec);
      for(int i=1;i<=len;++i){
        ans.a[i] += a[i]+b.a[i]; //加位
        if(ans.a[i]>=base){//需要进位
          ans.a[i+1]++;//进位
          ans.a[i]-=base;
        }
      }
      ans._len_big_dec=ans.a[len+1]?len+1:len+0; //判断最高位是否需要进位
    }else{//异号的情况
      big_dec c,d; // c的绝对值小于d
      c = min(this->abs(),b.abs());
      d = max(this->abs(),b.abs());
      ans.f = d.f;//结果与绝对值大的相同
      int len = max(c._len_big_dec,d._len_big_dec);
      for(int i=1;i<=len;++i){
        //如果当前位小于等于c的长度，就减去c的当前位，否则减去0
        ans.a[i] += d.a[i]-(i<=c._len_big_dec?c.a[i]:0);
        if(ans.a[i] < 0){// 需要借位
          ans.a[i] += base; // 加上基数
          ans.a[i+1]--; // 借位
        }
      }
      while(len>1 &&(ans.a[len] == 0)) len--;//去除前导0
      ans._len_big_dec = len;//更新
    }
    return ans;
  }

  //乘法(On^2)
  big_dec operator * (const big_dec &b){
    big_dec ans;
    ans.f = f^b.f;//异或就可以，一样的是正也就是0，不一样的是负也就是1
    for(int i=1;i<=_len_big_dec;++i){
      for(int j=1;j<=b._len_big_dec;++j){
        ans.a[i+j-1] += a[i]*b.a[j];//乘
        if(ans.a[i+j-1]>=base){//需要进位
          ans.a[i+j] += ans.a[i+j-1]/base;//要除基本的倍数
          ans.a[i+j-1] %= base;//mod一下
        }
      }
    }
    int max_len = _len_big_dec+b._len_big_dec;//最大的可能位数
    while(max_len>1 && ans.a[max_len]==0) max_len--;//同样的去除前导0
    ans._len_big_dec = max_len;//赋值
    return ans;
  }

  //相反数
  big_dec operator-() const {
    big_dec ret = *this;
    ret.f = !f; // 符号取反
    return ret;
  }

  //减法,直接加相反数
  big_dec operator - (const big_dec &b){
    big_dec ans ; 
    ans = *this + -b;
    if(*this<b){
      ans.f = !ans.f;
    }
    return ans;
  }

  // to_int
  int to_int() const {
    int ans = 0;
    for (int i=_len_big_dec;i>=1;--i) {
      ans = ans*base+a[i];
    }
    return f ? -ans : ans;
  }
  // to_long_long
  long long to_long_long() const {
    long long ans = 0;
    for (int i=_len_big_dec;i>=1;--i) {
      ans = ans*base+a[i];
    }
    return f ? -ans : ans;
  }
} ;

int main(){
  big_dec a, b, ans;
  char str[10086];

  printf("a:");
  scanf("%s", str);
  a.read_from_str(str);

  printf("b:");
  scanf("%s", str);
  b.read_from_str(str);

  printf("Big Decimal value:\n"); //高精度十进制数值
  printf("a:");a.print_stdout();printf("\n");//输出
  printf("b:");b.print_stdout();printf("\n");//输出

  printf("To int and long long,maybe overflow:\n");//转换为int和long long，可能会溢出
  printf("a_to_int: %d\n", a.to_int());//转换为int
  printf("a_to_long_long: %lld\n", a.to_long_long());//转换为long long
  printf("\n");
  printf("b_to_int: %d\n", b.to_int());//转换为int
  printf("b_to_long_long: %lld\n", b.to_long_long());//转换为long long
  printf("\n");

  ans = a + b;
  printf("a + b = ");//加法
  ans.print_stdout(); printf("\n");

  ans = a - b;
  printf("a - b = ");//减法
  ans.print_stdout(); printf("\n");

  ans = a * b;
  printf("a * b = ");//乘法
  ans.print_stdout(); printf("\n");
 

  return 0;
}

//测试样例1:
//114514
//1919810

//a:114514
//b:1919810
//Big Decimal value:
//a:114514
//b:1919810

//To int and long long,maybe overflow:
//a_to_int: 114514
//a_to_long_long: 114514
//
//b_to_int: 1919810
//b_to_long_long: 1919810
//
//a + b = 2034324
//a - b = -1805296
//a * b = 219845122340


//=========================================
//测试样例2:
//1145140000114514000
//-191981000019198100019198101919810

//输出：
// a:1145140000114514000
// b:-191981000019198100019198101919810
// Big Decimal value:
// a:1145140000114514000
// b:-191981000019198100019198101919810

// To int and long long,maybe overflow:
// a_to_int: 1290442832
// a_to_long_long: 1145140000114514000 (这里正确转换了，还没有溢出longlong)
// 
// b_to_int: -181246018
// b_to_long_long: 5304828336058558398
// 
// a + b = 191981000019196954879197987405810
// a - b = 191981000019199245159198216433810
// a * b = -219845122383969024492182965658049674843245122340000

//py3.11输出结果:-219845122383969024492182965658049674843245122340000