大数模板
发布时间:2020-12-14 01:16:59 所属栏目:大数据 来源:网络整理
导读:我花了很长时间写的大数模板,过了很多题,但是我相信还是有BUG的,欢迎大家指出! 这套模板目前已经实现了大数开方,四则运算,大数比较等功能,后面还有其他功能,我会陆续更新。 大数模板 struct BigInteger { vector int s; //12345--54321 void DealZer
我花了很长时间写的大数模板,过了很多题,但是我相信还是有BUG的,欢迎大家指出! struct BigInteger {
vector<int>s; //12345--54321
void DealZero() { //处理前导0
for(int i = s.size() - 1; i > 0; --i){
if(s[i] == 0) s.pop_back();
else break;
}
}
BigInteger operator = (long long num) { // 赋值运算符
s.clear();
vector<int>tmp;
do{
s.push_back(num % 10);
num /= 10;
}while(num);
return *this;
}
BigInteger operator = (const string& str) { // 赋值运算符
s.clear();
for(int i = str.size() - 1; i >= 0; --i) s.push_back(str[i] - '0');
this->DealZero();
return *this;
}
BigInteger operator + (const BigInteger& b) const {
BigInteger c;
c.s.clear();
int len1 = s.size(),len2 = b.s.size();
for(int i = 0,g = 0; g > 0 || i < len1 || i < len2; ++i) {
int x = g;
if(i < len1) x += s[i];
if(i < len2) x += b.s[i];
c.s.push_back(x % 10);
g = x / 10;
}
return c;
}
//大数减小数
BigInteger operator - (const BigInteger& b) const {
BigInteger c;
c.s.clear();
int len1 = s.size(),g = 0; i < len1 || i < len2; ++i) {
int x = g;
if(i < len1) x += s[i];
g = 0;
if(i < len2) x -= b.s[i];
if(x < 0) {
g = -1; //借位
x += 10;
}
c.s.push_back(x);
}
c.DealZero();
return c;
}
BigInteger operator * (const BigInteger& b) const {
BigInteger c,tmp;
c.s.clear();
int len1 = s.size(),len2 = b.s.size();
for(int i = 0; i < len1; ++i) {
tmp.s.clear();tmp;
int num = i;
while(num--) tmp.s.push_back(0);
int g = 0;
for(int j = 0; j < len2; ++j) {
int x = s[i] * b.s[j] + g;
tmp.s.push_back(x % 10);
g = x / 10;
}
if(g > 0) tmp.s.push_back(g);
c = c + tmp;
}
c.DealZero();
return c;
}
//单精度除法
BigInteger operator / (const int b) const {
BigInteger c,tmp;
c.s.clear();
int len = s.size();
int div = 0;
for(int i = len - 1; i >= 0; --i) {
div = div * 10 + s[i];
while(div < b && i > 0) {
div = div * 10 + s[--i];
}
tmp.s.push_back(div / b);
div %= b;
}
for(int i = tmp.s.size() - 1; i >= 0; --i) c.s.push_back(tmp.s[i]);
c.DealZero();
return c;
}
bool operator < (const BigInteger& b) const {
int len1 = s.size(),len2 = b.s.size();
if(len1 != len2) return len1 < len2;
for(int i = len1 - 1; i >= 0; --i) {
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false; //相等
}
bool operator <= (const BigInteger& b) const {
return !(b < *this);
}
string ToStr() {
string ans;
ans.clear();
for(int i = s.size()-1; i >= 0; --i)
ans.push_back(s[i] + '0');
return ans;
}
//大数开方
/**大数开方用法说明: 字符串必须从第二个位置开始输入,且s[0] = '0' scanf("%s",s+1); */
BigInteger SQRT(char *s) {
string p = "";
s[0]='0';
if(strlen(s)%2 == 1)
work(p,2,s+1,0);
else
work(p,s,0);
BigInteger c;
c.s.clear();
c = p;
return c;
}
//开方准备
//------------------------------------
int l;
int work(string &p,int o,char *O,int I){
char c,*D=O ;
if(o>0)
{
for(l=0;D[l];D[l++]-=10)
{
D[l++]-=120;
D[l]-=110;
while(!work(p,0,O,l))
D[l]+=20;
p += (char)((D[l]+1032)/20);
}
}
else
{
c=o+(D[I]+82)%10-(I>l/2)*(D[I-l+I]+72)/10-9;
D[I]+=I<0 ? 0 : !(o=work(p,c/10,I-1))*((c+999)%10-(D[I]+92)%10);
}
return o;
}
//-----------------------------------------
};
ostream& operator << (ostream &out,const BigInteger& x) {
for(int i = x.s.size() - 1; i >= 0; --i)
out << x.s[i];
return out;
}
istream& operator >> (istream &in,BigInteger& x) {
string s;
if(!(in >> s)) return in;
x = s;
return in;
}
我相信肯定是有BUG,大家如果发现了请一定指出!谢谢! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |