#include <iostream> #include <stdio.h> #include <string> #include <string.h> #include <math.h> #include <queue> #include <memory.h> using namespace std; #define bigNum_size 220 //大数的段数,bigNum能表示的最大长度 = bigNum_size*log(mod) #define mod 100000 //每段存储数字的长度为0的个数 char A[1010], B[1010]; struct bigNum { int a[bigNum_size]; int len;//存储大数的段数,初始化时长度都为1,表示的值默认为0 bigNum() { len = 1; memset(a, 0, sizeof(a)); } bigNum(char *str) { int n = strlen(str); int t = 0; int m, i, k = 0, inf = 1; memset(a, 0, sizeof(a)); for (i = n - 1; i >= 0; i--) { m = str[i] - '0'; k += inf*m; inf *= 10; if (inf == mod) { inf = 1; a[t++] = k; k = 0; } } a[t++] = k; while (t > 1 && a[t-1] == 0) t--; len = t; } bigNum(int x) { memset(a, 0, sizeof(a)); a[0] = x; int i = 1; while (a[i-1] >= mod) { a[i] = a[i-1]/mod; a[i-1] %= mod; i++; } len = i; } }; bigNum operator +(bigNum x, bigNum y) //重载运算符"+",执行两个大数的加法并返回结果 { int i, n; bigNum s; if (x.len < y.len) { bigNum temp = x; x = y; y = temp; } n = y.len; for (i = 0; i < n; i++) { x.a[i] += y.a[i]; x.a[i+1] += x.a[i]/mod; x.a[i] %= mod; } while (x.a[n] > mod) { x.a[n+1] += x.a[n]/mod; n++; } if (x.a[x.len])x.len++; return x; } bigNum operator *(int m, bigNum x) //重载运算符"*",执行一个大数乘以一个int内的数字,并返回结果 { int i, k = 0; for (i = 0; i < x.len; i++) { x.a[i] = x.a[i] * m + k; k = x.a[i] / mod; x.a[i] %= mod; } while (k) { x.a[i] = k%mod; k /= mod; i++; } x.len = i; return x; } bool operator < (bigNum x, bigNum y) //比较两个大数的大小,如果x<y返回true,否则返回false { if (x.len < y.len) return true; if (x.len > y.len) return false; int i; for (i = x.len - 1; i >= 0; i--) if (x.a[i] < y.a[i]) return true; else if (x.a[i] > y.a[i]) return false; return false; } bigNum operator - (bigNum x, bigNum y) //计算两个大数的减法,其中保证x>y。 { bigNum s; int i; int k = 0; for (i = 0; i < y.len; i++) { if (x.a[i] == -1) { x.a[i] = mod - 1; x.a[i+1]--; } if (x.a[i] >= y.a[i]) s.a[i] = x.a[i] - y.a[i]; else { s.a[i] = mod + x.a[i] - y.a[i]; x.a[i+1]--; } } while (i < x.len) { if (x.a[i] == -1) { x.a[i] = mod - 1; x.a[i+1]--; } s.a[i] = x.a[i]; i++; } s.len = i; while (s.a[s.len - 1] == 0) { s.len--; } if (s.len == 0) s.len = 1; return s; } bigNum sqrt_bignum(bigNum x) //开根号,只能对大的正整数开方求得整数不分, //如果要对小数开方或对正整数开方求小数点后面的数字, //可以将这个数扩大10^(2*k)倍在进行开方。 // 在调用开发函数时, mod = 10 才能完成。所以效率不是很高。 { bigNum s, md; bigNum p; bigNum temp; int n = x.len; int k; int i; if (n%2) { if (x.a[n-1] > 8) { s.a[0] = 3; md.a[0] = x.a[n-1] - 9; } else if (x.a[n-1] > 3) { s.a[0] = 2; md.a[0] = x.a[n-1] - 4; } else { s.a[0] = 1; md.a[0] = x.a[n-1] - 1; } n--; } for (i = n - 1; i > 0; i = i - 2) { p.a[1] = x.a[i]; p.a[0] = x.a[i-1]; p.len = 2; md = (100 * md + p); for (k = 1; k < 10; k++) { p.a[0] = k; p.len = 1; temp = 20*s + p; temp = k*temp; if (md < temp) break; } k--; p.a[0] = k; p.len = 1; temp = 20*s + p; temp = k*temp; md = md - temp; s = 10*s + p; } return s; } void output(bigNum x) //输出大数的函数 { int i; int n = x.len; printf("%d", x.a[n-1]); for (i = n - 2; i >= 0; i--) printf("%05d", x.a[i]);// %d05d与mod大小有关,即每段的数字个数。 printf("\n"); } int main() { return 0; }
原文链接: https://www.cnblogs.com/noonoo/archive/2011/06/16/2083039.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/27267
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!