C++ BigInteger模板
2024-09-03 10:37:58
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std; #define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
const long long MOD = ;
class BigInteger
{
private:
int a[]; //可以控制大数的位数
int len; //大数长度
public:
BigInteger(){ len = ; memset(a, , sizeof(a)); } //构造函数
BigInteger(const int); //将一个int类型的变量转化为大数
BigInteger(const char*); //将一个字符串类型的变量转化为大数
BigInteger(const BigInteger &); //拷贝构造函数
BigInteger &operator=(const BigInteger &); //重载赋值运算符，大数之间进行赋值运算 friend istream& operator>>(istream&, BigInteger&); //重载输入运算符
friend ostream& operator<<(ostream&, BigInteger&); //重载输出运算符 BigInteger operator+(const BigInteger &) const; //重载加法运算符，两个大数之间的相加运算
BigInteger operator-(const BigInteger &) const; //重载减法运算符，两个大数之间的相减运算
BigInteger operator*(const BigInteger &) const; //重载乘法运算符，两个大数之间的相乘运算
BigInteger operator/(const int &) const; //重载除法运算符，大数对一个整数进行相除运算 BigInteger operator^(const int &) const; //大数的n次方运算
long long operator%(const long long &) const; //大数对一个int类型的变量进行取模运算
bool operator>(const BigInteger & T)const; //大数和另一个大数的大小比较
bool operator>(const int & t)const; //大数和一个int类型的变量的大小比较 void print(); //输出大数
};
BigInteger::BigInteger(const int b) //将一个int类型的变量转化为大数
{
int c, d = b;
len = ;
memset(a, , sizeof(a));
while (d > MAXN)
{
c = d - (d / (MAXN + )) * (MAXN + );
d = d / (MAXN + );
a[len++] = c;
}
a[len++] = d;
}
BigInteger::BigInteger(const char*s) //将一个字符串类型的变量转化为大数
{
int t, k, index, l, i;
memset(a, , sizeof(a));
l = strlen(s);
len = l / DLEN;
if (l%DLEN)
len++;
index = ;
for (i = l - ; i >= ; i -= DLEN)
{
t = ;
k = i - DLEN + ;
if (k<)
k = ;
for (int j = k; j <= i; j++)
t = t * + s[j] - '';
a[index++] = t;
}
}
BigInteger::BigInteger(const BigInteger & T) : len(T.len) //拷贝构造函数
{
int i;
memset(a, , sizeof(a));
for (i = ; i < len; i++)
a[i] = T.a[i];
}
BigInteger & BigInteger::operator=(const BigInteger & n) //重载赋值运算符，大数之间进行赋值运算
{
int i;
len = n.len;
memset(a, , sizeof(a));
for (i = ; i < len; i++)
a[i] = n.a[i];
return *this;
}
istream& operator>>(istream & in, BigInteger & b) //重载输入运算符
{
char ch[MAXSIZE * ];
int i = -;
in >> ch;
int l = strlen(ch);
int count = , sum = ;
for (i = l - ; i >= ;)
{
sum = ;
int t = ;
for (int j = ; j< && i >= ; j++, i--, t *= )
{
sum += (ch[i] - '')*t;
}
b.a[count] = sum;
count++;
}
b.len = count++;
return in; }
ostream& operator<<(ostream& out, BigInteger& b) //重载输出运算符
{
int i;
cout << b.a[b.len - ];
for (i = b.len - ; i >= ; i--)
{
cout.width(DLEN);
cout.fill('');
cout << b.a[i];
}
return out;
} BigInteger BigInteger::operator+(const BigInteger & T) const //两个大数之间的相加运算
{
BigInteger t(*this);
int i, big; //位数
big = T.len > len ? T.len : len;
for (i = ; i < big; i++)
{
t.a[i] += T.a[i];
if (t.a[i] > MAXN)
{
t.a[i + ]++;
t.a[i] -= MAXN + ;
}
}
if (t.a[big] != )
t.len = big + ;
else
t.len = big;
return t;
}
BigInteger BigInteger::operator-(const BigInteger & T) const //两个大数之间的相减运算
{
int i, j, big;
bool flag;
BigInteger t1, t2;
if (*this>T)
{
t1 = *this;
t2 = T;
flag = ;
}
else
{
t1 = T;
t2 = *this;
flag = ;
}
big = t1.len;
for (i = ; i < big; i++)
{
if (t1.a[i] < t2.a[i])
{
j = i + ;
while (t1.a[j] == )
j++;
t1.a[j--]--;
while (j > i)
t1.a[j--] += MAXN;
t1.a[i] += MAXN + - t2.a[i];
}
else
t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[t1.len - ] == && t1.len > )
{
t1.len--;
big--;
}
if (flag)
t1.a[big - ] = - t1.a[big - ];
return t1;
} BigInteger BigInteger::operator*(const BigInteger & T) const //两个大数之间的相乘运算
{
BigInteger ret;
int i, j, up;
int temp, temp1;
for (i = ; i < len; i++)
{
up = ;
for (j = ; j < T.len; j++)
{
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if (temp > MAXN)
{
temp1 = temp - temp / (MAXN + ) * (MAXN + );
up = temp / (MAXN + );
ret.a[i + j] = temp1;
}
else
{
up = ;
ret.a[i + j] = temp;
}
}
if (up != )
ret.a[i + j] = up;
}
ret.len = i + j;
while (ret.a[ret.len - ] == && ret.len > )
ret.len--;
return ret;
}
BigInteger BigInteger::operator/(const int & b) const //大数对一个整数进行相除运算
{
BigInteger ret;
int i, down = ;
for (i = len - ; i >= ; i--)
{
ret.a[i] = (a[i] + down * (MAXN + )) / b;
down = a[i] + down * (MAXN + ) - ret.a[i] * b;
}
ret.len = len;
while (ret.a[ret.len - ] == && ret.len > )
ret.len--;
return ret;
}
long long BigInteger::operator %(const long long & b) const //大数对一个int类型的变量进行取模运算
{
int i;
long long d = ;
for (i = len - ; i >= ; i--)
{
d = ((d * (MAXN + )) % b + (long long)(a[i])) % b;
}
return d;
}
BigInteger BigInteger::operator^(const int & n) const //大数的n次方运算
{
BigInteger t, ret();
int i;
if (n<)
exit(-);
if (n == )
return ;
if (n == )
return *this;
int m = n;
while (m>)
{
t = *this;
for (i = ; i << <= m; i <<= )
{
t = t*t;
}
m -= i;
ret = ret*t;
if (m == )
ret = ret*(*this);
}
return ret;
}
bool BigInteger::operator>(const BigInteger & T) const //大数和另一个大数的大小比较
{
int ln;
if (len > T.len)
return true;
else if (len == T.len)
{
ln = len - ;
while (a[ln] == T.a[ln] && ln >= )
ln--;
if (ln >= && a[ln] > T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigInteger::operator >(const int & t) const //大数和一个int类型的变量的大小比较
{
BigInteger b(t);
return *this>b;
} void BigInteger::print() //输出大数
{
int i;
cout << a[len - ];
for (i = len - ; i >= ; i--)
{
cout.width(DLEN);
cout.fill('');
cout << a[i];
}
cout << endl;
}
其实这个也没多大用，大数肯定直接用Java了
最新文章
- HDOJ 1008. Elevator 简单模拟水题
- Android中的XML解析
- WPF 设置透明度和圆形图片
- Pattern和Matcher
- SharePoint 2010 中使用Ztree和EasyUI样式冲突问题
- C#_字符串的操作
- SQL第二课-创建数据表
- 【译】iOS人性化界面指南(iOS Human Interface Guidelines)(一)
- YUI Array 之dedupe(快速去重)
- Jenkins持续集成项目搭建与实践——基于Python Selenium自动化测试（自由风格）
- Thread线程join方法自我理解
- 以超级管理员方式运行bat文件
- C++ Opencv createTrackbar()创建滑动条实现对比度、亮度调节及注意事项
- HTML5-CSS3-JavaScript(1)
- Linux下安装与卸载anaconda
- Please restart this script from an administrative PowerShell
- EasyUI效果--DataGrid的编辑效果
- [转]JVM性能调优监控工具
- [Python 网络编程] TCP Client (四)
- SSIS实践入门3：把SSIS程序包从A电脑到B电脑的转移