Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hnust_zhuminhao","updateTime":1487000157000,"title":"c++ 大数模板","dislikeCnt":0,"content":"取自kuangbin\n```\nclass BigNum \n{ \npublic: \n BigNum(){ len \u003d 1; memset(a, 0, sizeof(a)); } //构造函数 \n BigNum(const int); //将一个int类型的变量转化为大数 \n BigNum(const char*); //将一个字符串类型的变量转化为大数 \n BigNum(const BigNum \u0026); //拷贝构造函数 \n BigNum \u0026operator\u003d(const BigNum \u0026); //重载赋值运算符,大数之间进行赋值运算 \n \n friend istream\u0026 operator\u003e\u003e(istream\u0026, BigNum\u0026); //重载输入运算符 \n friend ostream\u0026 operator\u003c\u003c(ostream\u0026, BigNum\u0026); //重载输出运算符 \n \n BigNum operator+(const BigNum \u0026) const; //重载加法运算符,两个大数之间的相加运算 \n BigNum operator-(const BigNum \u0026) const; //重载减法运算符,两个大数之间的相减运算 \n BigNum operator*(const BigNum \u0026) const; //重载乘法运算符,两个大数之间的相乘运算 \n BigNum operator/(const int \u0026) const; //重载除法运算符,大数对一个整数进行相除运算 \n \n BigNum operator^(const int \u0026) const; //大数的n次方运算 \n int operator%(const int \u0026) const; //大数对一个int类型的变量进行取模运算 \n bool operator\u003e(const BigNum \u0026 T)const; //大数和另一个大数的大小比较 \n bool operator\u003e(const int \u0026 t)const; //大数和一个int类型的变量的大小比较 \n \n void print(); //输出大数 \n int a[500]; //可以控制大数的位数 \n int len; //大数长度 \n}; \n//将一个int类型的变量转化为大数 \nBigNum::BigNum(const int b) { \n int c, d \u003d b; \n len \u003d 0; \n memset(a, 0, sizeof(a)); \n while (d \u003e MAXN) { \n c \u003d d - (d / (MAXN + 1)) * (MAXN + 1); \n d \u003d d / (MAXN + 1); \n a[len++] \u003d c; \n } \n a[len++] \u003d d; \n} \n//将一个字符串类型的变量转化为大数 \nBigNum::BigNum(const char* s) { \n int t, k, index, l; \n memset(a, 0, sizeof(a)); \n l \u003d strlen(s); \n len \u003d l / DLEN; \n if (l % DLEN) len++; \n index \u003d 0; \n for (int i \u003d l-1; i \u003e\u003d 0; i -\u003d DLEN) { \n t \u003d 0; \n k \u003d i-DLEN+1; \n if (k \u003c 0) k \u003d 0; \n for (int j \u003d k; j \u003c\u003d i; j++) t \u003d t * 10 + s[j] - \u00270\u0027; \n a[index++] \u003d t; \n } \n} \n //拷贝构造函数 \nBigNum::BigNum(const BigNum \u0026 T) : len(T.len) { \n memset(a, 0, sizeof(a)); \n for (int i \u003d 0; i \u003c len; i++) a[i] \u003d T.a[i]; \n} \n //重载赋值运算符,大数之间进行赋值运算 \nBigNum \u0026 BigNum::operator \u003d (const BigNum \u0026 n) { \n len \u003d n.len; \n memset(a, 0, sizeof(a)); \n for (int i \u003d 0; i \u003c len; i++) a[i] \u003d n.a[i]; \n return *this; \n} \n//重载输入运算符 \nistream\u0026 operator \u003e\u003e (istream \u0026 in, BigNum \u0026 b) { \n char ch[MAXSIZE * 4]; \n in \u003e\u003e ch; \n int l \u003d strlen(ch); \n int cnt \u003d 0, sum \u003d 0; \n for (int i \u003d l-1; i \u003e\u003d 0;) { \n sum \u003d 0; \n int t \u003d 1; \n for (int j \u003d 0; j \u003c 4 \u0026\u0026 i \u003e\u003d 0; j++, i--, t *\u003d 10) sum +\u003d (ch[i] - \u00270\u0027) * t; \n b.a[cnt++] \u003d sum; \n } \n b.len \u003d cnt++; \n return in; \n} \n//重载输出运算符 \nostream\u0026 operator \u003c\u003c (ostream\u0026 out, BigNum\u0026 b) { \n cout \u003c\u003c b.a[b.len - 1]; \n for (int i \u003d b.len - 2 ; i \u003e\u003d 0 ; i--) { \n cout.width(DLEN); \n cout.fill(\u00270\u0027); \n cout \u003c\u003c b.a[i]; \n } \n return out; \n} \n//两个大数之间的相加运算 \nBigNum BigNum::operator + (const BigNum \u0026 T) const { \n BigNum t(*this); \n int big\u003d T.len \u003e len ? T.len : len; //位数 \n for (int i \u003d 0 ; i \u003c big ; i++) { \n t.a[i] +\u003d T.a[i]; \n if (t.a[i] \u003e MAXN){ \n t.a[i + 1]++; \n t.a[i] -\u003d MAXN + 1; \n } \n } \n t.a[big] ? t.len \u003d big + 1 : t.len \u003d big; \n return t; \n} \n//两个大数之间的相减运算 \nBigNum BigNum::operator - (const BigNum \u0026 T) const { \n int big; \n bool flag; \n BigNum t1, t2; \n if (*this \u003e T) { \n t1 \u003d *this; \n t2 \u003d T; \n flag \u003d 0; \n } \n else { \n t1 \u003d T; \n t2 \u003d *this; \n flag \u003d 1; \n } \n big \u003d t1.len; \n for (int i \u003d 0 ; i \u003c big ; i++) { \n if(t1.a[i] \u003c t2.a[i]) { \n int j \u003d i + 1; \n while (t1.a[j] \u003d\u003d 0) j++; \n t1.a[j--]--; \n while(j \u003e i) t1.a[j--] +\u003d MAXN; \n t1.a[i] +\u003d MAXN + 1 - t2.a[i]; \n } \n else t1.a[i] -\u003d t2.a[i]; \n } \n t1.len \u003d big; \n while (t1.a[len - 1] \u003d\u003d 0 \u0026\u0026 t1.len \u003e 1) t1.len--, big--; \n if (flag) t1.a[big-1] \u003d 0 - t1.a[big-1]; \n return t1; \n} \n//两个大数之间的相乘运算 \nBigNum BigNum::operator * (const BigNum \u0026 T) const { \n BigNum ret; \n int up, i, j; \n int temp, temp1; \n for (i \u003d 0 ; i \u003c len ; i++) { \n up \u003d 0; \n for (j \u003d 0 ; j \u003c T.len ; j++) { \n temp \u003d a[i] * T.a[j] + ret.a[i + j] + up; \n if (temp \u003e MAXN) { \n temp1 \u003d temp - temp / (MAXN + 1) * (MAXN + 1); \n up \u003d temp / (MAXN + 1); \n ret.a[i + j] \u003d temp1; \n } \n else { \n up \u003d 0; \n ret.a[i + j] \u003d temp; \n } \n } \n if(up !\u003d 0) ret.a[i + j] \u003d up; \n } \n ret.len \u003d i + j; \n while(ret.a[ret.len - 1] \u003d\u003d 0 \u0026\u0026 ret.len \u003e 1) ret.len--; \n return ret; \n} \n //大数对一个整数进行相除运算 \nBigNum BigNum::operator / (const int \u0026 b) const { \n BigNum ret; \n int down \u003d 0; \n for(int i \u003d len - 1; i \u003e\u003d 0 ; i--) { \n ret.a[i] \u003d (a[i] + down * (MAXN + 1)) / b; \n down \u003d a[i] + down * (MAXN + 1) - ret.a[i] * b; \n } \n ret.len \u003d len; \n while (ret.a[ret.len - 1] \u003d\u003d 0 \u0026\u0026 ret.len \u003e 1) ret.len--; \n return ret; \n} \n//大数对一个int类型的变量进行取模运算 \nint BigNum::operator % (const int \u0026 b) const { \n int d \u003d 0; \n for (int i \u003d len-1; i \u003e\u003d 0; i--) d \u003d ((d * (MAXN+1)) % b + a[i]) % b; \n return d; \n} \n //大数的n次方运算 \nBigNum BigNum::operator ^ (const int \u0026 n) const { \n BigNum t, ret(1); \n if (n \u003c 0) exit(-1); \n if (n \u003d\u003d 0) return 1; \n if (n \u003d\u003d 1) return *this; \n int m \u003d n, i; \n while (m \u003e 1) { \n t \u003d *this; \n for (i \u003d 1; i \u003c\u003c 1 \u003c\u003d m; i \u003c\u003c\u003d 1) t \u003d t * t; \n m -\u003d i; \n ret \u003d ret * t; \n if (m \u003d\u003d 1) ret \u003d ret * (*this); \n } \n return ret; \n} \n//大数和另一个大数的大小比较 \nbool BigNum::operator \u003e (const BigNum \u0026 T) const { \n int ln; \n if (len \u003e T.len) return true; \n else if (len \u003d\u003d T.len) { \n ln \u003d len - 1; \n while (a[ln] \u003d\u003d T.a[ln] \u0026\u0026 ln \u003e\u003d 0) ln--; \n if (ln \u003e\u003d 0 \u0026\u0026 a[ln] \u003e T.a[ln]) return true; \n else return false; \n } \n return false; \n} \n//大数和一个int类型的变量的大小比较 \nbool BigNum::operator \u003e (const int \u0026 t) const { \n BigNum b(t); \n return *this \u003e b; \n} \n//输出大数 \nvoid BigNum::print() { \n cout \u003c\u003c a[len - 1]; \n for(int i \u003d len - 2 ; i \u003e\u003d 0 ; i--) { \n cout.width(DLEN); \n cout.fill(\u00270\u0027); \n cout \u003c\u003c a[i]; \n } \n cout \u003c\u003c endl; \n} \n```\n","likeCnt":0,"createTime":1487000157000,"isWorkbook":false,"viewCnt":1283,"openness":1,"fav":false,"id":60,"trustable":false}