大数模板
发布时间:2020-12-14 01:33:59 所属栏目:大数据 来源:网络整理
导读:用了交大的模板,增加了base进制,有个地方要注意的是,base 不能开太大,因为在做加法或者乘法的时候,有可能就发生溢出了,如果是开int数组,那最好base = 10^5, 还有,maxn也不能开太大,否则会出错,下面模板base = 10^5,maxn开10^6次方爆掉还不知道什
用了交大的模板,增加了base进制,有个地方要注意的是,base 不能开太大,因为在做加法或者乘法的时候,有可能就发生溢出了,如果是开int数组,那最好base = 10^5, 还有,maxn也不能开太大,否则会出错,下面模板base = 10^5,maxn开10^6次方爆掉还不知道什么原因 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Hp_integer { static const int base = 100000; static const int width = 5;//base后有width个0 static const int maxn = 100000; int num[maxn],cnt; char s3[maxn]; void init() { cnt = 0; memset(num,sizeof(num)); } void print() { if (cnt == 0) { printf("0n"); return; } for (int i = cnt - 1; i >= 0; i--) { if (i == cnt - 1) printf("%d",num[i]); else printf("%05d",num[i]); } printf("n"); } int comp(const Hp_integer &b) { if (cnt > b.cnt) return 1; if (cnt < b.cnt) return -1; int i = cnt - 1; while (i > 0 && num[i] == b.num[i]) i--; return num[i] - b.num[i]; } bool operator > (const Hp_integer &b) { return this->comp(b) > 0; } bool operator >= (const Hp_integer &b) { return this->comp(b) >= 0; } bool operator < (const Hp_integer &b) { return this->comp(b) < 0; } bool operator <= (const Hp_integer &b) { return this->comp(b) <= 0; } bool operator == (const Hp_integer &b) { return this->comp(b) == 0; } bool operator != (const Hp_integer &b) { return this->comp(b) != 0; } Hp_integer operator = (const Hp_integer &b) { cnt = b.cnt; for (int i = 0; i < b.cnt; i++) num[i] = b.num[i]; return (*this); } Hp_integer operator = (const char *s) { int len = strlen(s),x; int l = (len - 1) / width + 1; cnt = 0; for (int i = 0; i < l; i++) { int end = len - i * width; int start = max(0,end - width); strncpy(s3,s + start,end - start); s3[end - start] = ' '; sscanf(s3,"%d",&x); num[cnt++] = x; } return (*this); } Hp_integer operator + (const Hp_integer &b) { Hp_integer c; c.init(); for (int i = 0; i < cnt || i < b.cnt; i++) { if (i < cnt) c.num[i] += num[i]; if (i < b.cnt) c.num[i] += b.num[i]; c.num[i + 1] = c.num[i] / base; c.num[i] %= base; } c.cnt = max(cnt,b.cnt) + 1; while (c.cnt > 1 && c.num[c.cnt - 1] == 0) c.cnt--; return c; } Hp_integer operator += (const Hp_integer &b) { (*this) = (*this) + b; return (*this); } Hp_integer operator - (const Hp_integer &b) { Hp_integer c; c.init(); for (int i = 0,j = 0,g = 0; i < cnt; i++,j++) { int x = -g; if (i < cnt) x += num[i]; if (i < b.cnt) x -= b.num[i]; if (x >= 0) g = 0; else { g = 1; x += base; } c.num[c.cnt++] = x; } while (c.cnt > 1 && c.num[c.cnt - 1] == 0) c.cnt--; return c; } Hp_integer operator -=(const Hp_integer &b) { (*this) = (*this) - b; return (*this); } Hp_integer operator * (const Hp_integer &b) const { Hp_integer c; c.init(); for (int i = 0; i < cnt; i++) { for (int j = 0; j < b.cnt; j++) { c.num[i + j] += num[i] * b.num[j]; c.num[i + j + 1] += c.num[i + j] / base; c.num[i + j] %= base; } } c.cnt = cnt + b.cnt; while (c.cnt > 1 && c.num[c.cnt - 1] == 0) c.cnt--; return c; } Hp_integer operator *= (const Hp_integer &b) { (*this) = (*this) * b; return (*this); } Hp_integer operator / (const Hp_integer &b) { Hp_integer c,d; c.init(),d.init(); if (b.cnt == 1 && b.num[0] == 0) return c; for (int i = cnt - 1; i >= 0; i--) { if (d.cnt != 1 || d.num[0] != 0) { for (int j = d.cnt; j > 0; j--) d.num[j] = d.num[j - 1]; d.cnt++; } d.num[0] = num[i]; c.num[i] = 0; while (d >= b) { d -= b; c.num[i]++; } } c.cnt = cnt; while (c.cnt > 1 && c.num[c.cnt - 1] == 0) c.cnt--; return c; } Hp_integer operator /= (const Hp_integer &b) { (*this) = (*this) / b; return (*this); } Hp_integer operator % (const Hp_integer &b) { Hp_integer c; c.init(); if (b.cnt == 1 && b.num[0] == 0) return c; for (int i = cnt - 1; i >= 0; i--) { if (c.cnt != 1 || c.num[0] != 0) { for (int j = c.cnt; i > 0; i--) c.num[j] = c.num[j - 1]; c.cnt++; } c.num[0] = num[i]; while (c >= b) c -= b; } return c; } Hp_integer operator %= (const Hp_integer &b) { (*this) = (*this) % b; return (*this); } }; int main() { char s1[10000],s2[10000]; while (true) { Hp_integer a,b,c; a.init(); b.init(); c.init(); scanf("%s%s",s1,s2); a = s1,b = s2; //c = a + b; //c.print(); //c = a - b; //c.print(); //c = a * b; //c.print(); //c = a / b; //c.print(); //c = a % b; //c.print(); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |