class="markdown_views prism-atom-one-light">

大数模板：

已重载的运算符运算符类型运算符双目运算符+(加), -(减), *(乘), /(整除), %(取模)关系运算符==(等于),　!=(不等于),　<(小于), >(大于), <=(小于等于), >=(大于等于)逻辑运算符||(逻辑或), &&(逻辑与), !(逻辑非)单目运算符+(正), -(负)自增自减运算符++(自增), –(自减)赋值运算符=, +=, -=, *=, /=, %=位运算符>>(右移运算符，与输入流关联), <<(左移运算符，与输出流关联)

---

支持的其他函数 函数声明 函数功能 size_t size() const 返回 BigInteger 对象的位数 BigInteger e(size_t n) const 返回 BigInteger 对象 × 10^n 后的值 BigInteger abs() const 返回 BigInteger 对象的绝对值

---

#include typedef long long ll; using namespace std; //大整数 struct BigInteger { static const int BASE = 100000000;//和WIDTH保持一致 static const int WIDTH = 8;//八位一存储,如修改记得修改输出中的%08d bool sign;//符号, 0表示负数 size_t length; vector num;//反序存 //构造函数 BigInteger (long long x = 0) { *this = x; } BigInteger (const string& x) { *this = x; } BigInteger (const BigInteger& x) { *this = x; } //剪掉前导0 void cutLeadingZero(){ while(num.back() == 0 && num.size() != 1) { num.pop_back(); } } //设置数的长度 void setLength(){ cutLeadingZero(); int tmp = num.back(); if(tmp == 0) { length = 1; } else{ length = (num.size() - 1) * WIDTH; while(tmp > 0) { ++length; tmp /= 10; } } } //赋值运算符 BigInteger& operator = (long long x) { num.clear(); if (x >= 0) sign = true; else { sign = false; x = -x; } do { num.push_back(x%BASE); x/=BASE; } while(x>0); setLength(); return *this; } //赋值运算符 BigInteger& operator = (const string& str) { num.clear(); sign = (str[0] != '-');//设置符号 int x, len=(str.size()-1-(!sign))/WIDTH+1; for(int i=0;i=num.size()&&i>=b.num.size()) break; int x=g; if(i=num.size()&&i>=b.num.size()) break; int x=g; g=0; if(i ansLL; for (int i = 0; i < lena+lenb; i++) ansLL.push_back(0); for (int i = 0; i < lena; i++){ for (int j = 0; j < lenb; j++){ ansLL[i+j] += (long long)num[i]*(long long)b.num[j]; } } while (ansLL.back() == 0 && ansLL.size() != 1) ansLL.pop_back(); int len = ansLL.size(); long long g = 0, tmp; BigInteger ans; ans.sign = (ansLL.size() == 1 && ansLL[0] == 0) || (sign == b.sign); ans.num.clear(); for (int i = 0; i < len; i++) { tmp = ansLL[i]; ans.num.push_back((tmp + g)%BASE); g = (tmp + g) / BASE; } if (g > 0) ans.num.push_back(g); ans.setLength(); return ans; } // / 运算符 (大数除小数) BigInteger operator / (const long long& b) const { BigInteger c; c.num.clear(); for(int i=0;i=0;i--) { c.num[i]=(num[i]+g*BASE)/b; g=num[i]+g*BASE-c.num[i]*b; } for(int i=num.size()-1;c.num[i]==0;i--){ c.num.pop_back(); } return c; } // /运算符 (大数除大数) BigInteger operator / (const BigInteger& b) const { BigInteger aa((*this).abs()); BigInteger bb(b.abs()); if (aa < bb) return 0; char *str = new char[aa.size() + 1]; memset(str, 0, sizeof(char)*(aa.size()+1)); BigInteger tmp; int lena = aa.length, lenb = bb.length; for (int i = 0; i <= lena - lenb; i++) { tmp = bb.e(lena - lenb - i); while (aa >= tmp) { ++str[i]; aa = aa - tmp; } str[i] += '0'; } BigInteger ans(str); delete[]str; ans.sign = (ans == 0 || sign == b.sign); return ans; } // % 运算符 (大数取模小数) BigInteger operator % (const long long& b) const { long long ans=0,lena=num.size(); for(int i=lena-1;i>=0;i--){ ans = (ans*BASE+num[i])%b; } return ans; } // %运算符 (大数取模大数) BigInteger operator % (const BigInteger& b) const{ return *this - *this / b * b; } BigInteger& operator ++ () { *this=*this+1;return *this; } // ++ 运算符 BigInteger& operator -- () { *this=*this-1;return *this; } // -- 运算符 BigInteger& operator += (const BigInteger& b) { *this=*this+b;return *this; } // += 运算符 BigInteger& operator -= (const BigInteger& b) { *this=*this-b;return *this; } // -= 运算符 BigInteger& operator *= (const BigInteger& b) { *this=*this*b;return *this; } // *=运算符 BigInteger& operator /= (const long long& b) { *this=*this/b;return *this; } // /=运算符 BigInteger& operator /= (const BigInteger& b) { *this=*this/b;return *this; } // /= 运算符 BigInteger& operator %= (const long long& b) { *this=*this%b;return *this; } // %=运算符 BigInteger& operator %= (const BigInteger& b) { *this=*this%b;return *this; } // %=运算符 // < 运算符 bool operator < (const BigInteger& b) const { if (sign && !b.sign) { return false; }//正负 else if(!sign && b.sign) { return true; }//负正 else if(!sign && !b.sign) { return -b < -*this; }//负负 //正正 if(num.size()!=b.num.size()) return num.size()=0;i--) if(num[i]!=b.num[i]) return num[i] (const BigInteger& b) const { return b<*this; } // > 运算符 bool operator <= (const BigInteger& b) const { return !(b<*this); } // <= 运算符 bool operator >= (const BigInteger& b) const { return !(*this= 运算符 bool operator != (const BigInteger& b) const { return b<*this||*this=0;i--) { char buf[10]; //如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d sprintf(buf,"%08d",x.num[i]); for(int j=0;j>使得可以直接输入大数 friend istream& operator >> (istream &in, BigInteger &x) { string str; in >> str; size_t len = str.size(); int i, start = 0; if (str[0] == '-') start = 1; if (str[start] == '