高精度乘法+劉汝佳BigNumber高精度結構體

高精度乘法，是指計算超過标準資料類型能夠表達的計算範圍的乘法計算。

如果計算機結果已經超過long long所能表示的範圍，将會得到溢出後的答案（結果不正确，也不能計算）

這時候就需要用到高精度乘法算法，所謂高精度乘法算法，就是通過錄入字元數組的形式儲存數字為字元串，然後逐一取出錄入的數字字元，轉換成對應的int數字進行計算，然後利用計算機善于重複循環處理資料的特點，模拟乘法豎式的計算過程，通過進位和錯位相加的形式，得到高精度計算結果。

#include<stdio.h>
#include<string.h>
int main()
{
	
	int c[100000]={0};
	int k=0,carry=0,x=1,i;
	char a[100000],b[100000];
	gets(a);
	gets(b);
	int  a_length=strlen(a),b_length=strlen(b);
	//乘法豎式的方法👇
	for( i=a_length-1;i>=0;i--)
	{
	  for(int j=b_length-1;j>=0;j--) 
	  {
	  	  c[k]=(a[i]-'0')*(b[j]-'0')+carry+c[k];
	  	  carry=c[k]/10;//carry 進位
	  	  c[k]%=10;
	  	  k++;
	  }
	  c[k]+=carry;//可能最高位有進位
	  carry=0;//被乘數的第k+1個數開始，carry清0
	  k=x;//————錯位相加
	  x++;
    }
    for( i=10000-1;i>0;i--)
	if(c[i]) break;//去掉前導0
	for(int j=i;j>=0;j--)
	printf("%d",c[j]);//逆序輸出
	return 0;
} 
           

最後是劉汝佳高精度結構體

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;

struct BigInteger {
  static const int BASE = 100000000;
  static const int WIDTH = 8;
  vector<int> s;

  BigInteger(long long num = 0) { *this = num; } // 構造函數
  BigInteger operator = (long long num) { // 指派運算符
    s.clear();
    do {
      s.push_back(num % BASE);
      num /= BASE;
    } while(num > 0);
    return *this;
  }
  BigInteger operator = (const string& str) { // 指派運算符
    s.clear();
    int x, len = (str.length() - 1) / WIDTH + 1;
    for(int i = 0; i < len; i++) {
      int end = str.length() - i*WIDTH;
      int start = max(0, end - WIDTH);
      sscanf(str.substr(start, end-start).c_str(), "%d", &x);
      s.push_back(x);
    }
    return *this;
  }
  BigInteger operator + (const BigInteger& b) const {
    BigInteger c;
    c.s.clear();
    for(int i = 0, g = 0; ; i++) {
      if(g == 0 && i >= s.size() && i >= b.s.size()) break;
      int x = g;
      if(i < s.size()) x += s[i];
      if(i < b.s.size()) x += b.s[i];
      c.s.push_back(x % BASE);
      g = x / BASE;
    }
    return c;
  }
};

ostream& operator << (ostream &out, const BigInteger& x) {
  out << x.s.back();
  for(int i = x.s.size()-2; i >= 0; i--) {
    char buf[20];
    sprintf(buf, "%08d", x.s[i]);
    for(int j = 0; j < strlen(buf); j++) out << buf[j];
  }
  return out;
}

istream& operator >> (istream &in, BigInteger& x) {
  string s;
  if(!(in >> s)) return in;
  x = s;
  return in;
}

#include<set>
#include<map>
set<BigInteger> s;
map<BigInteger, int> m;

int main() {
  BigInteger y;
  BigInteger x = y;
  BigInteger z = 123;

  BigInteger a, b;
  cin >> a >> b;
  cout << a + b << "\n";
//   cout << BigInteger::BASE << "\n";1
  return 0;
}