大数(高精度数)模板.doc

/高精度模板，注意本模板并没有考虑中间会出现负数的情况 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MAXL = 500; struct BigNum int numMAXL; int len; ; /高精度比较 a b return 1, a = b return 0; a b.len) ? 1 : -1; for(i = a.len-1; i = 0; i-) if(a.numi != b.numi) return (a.numi b.numi) ? 1 : -1; return 0; /高精度加法 BigNum Add(BigNum &a, BigNum &b) BigNum c; int i, len; len = (a.len b.len) ? a.len : b.len; memset(c.num, 0, sizeof(c.num); for(i = 0; i = 10) c.numi+1+; c.numi -= 10; if(c.numlen) len+; c.len = len; return c; /高精度减法,保证a = b BigNum Sub(BigNum &a, BigNum &b) BigNum c; int i, len; len = (a.len b.len) ? a.len : b.len; memset(c.num, 0, sizeof(c.num); for(i = 0; i len; i+) c.numi += (a.numi-b.numi); if(c.numi 1) len-; c.len = len; return c; /高精度乘以低精度，当b很大时可能会发生溢出int范围,具体情况具体分析 /如果b很大可以考虑把b看成高精度 BigNum Mul1(BigNum &a, int &b) BigNum c; int i, len; len = a.len; memset(c.num, 0, sizeof(c.num); /乘以0，直接返回0 if(b = 0) c.len = 1; return c; for(i = 0; i = 10) c.numi+1 = c.numi/10; c.numi %= 10; while(c.numlen 0) c.numlen+1 = c.numlen/10; c.numlen+ %= 10; c.len = len; return c; /高精度乘以高精度,注意要及时进位，否则肯能会引起溢出,但这样会增加算法的复杂度， /如果确定不会发生溢出, 可以将里面的while改成if BigNum Mul2(BigNum &a, BigNum &b) int i, j, len = 0; BigNum c; memset(c.num, 0, sizeof(c.num); for(i = 0; i a.len; i+) for(j = 0; j = 10) c.numi+j+1 += c.numi+j/10; c.numi+j %= 10; len = a.len+b.len-1; while(c.numlen-1 = 0 & len 1) len-; if(c.numlen) len+; c.len = len; return c; /高精度除以低精度,除的结果为c, 余数为f void Div1(BigNum &a, int &b, BigNum &c, int &f) int i, len = a.len; memset(c.num, 0, sizeof(c.num); f = 0; for(i = a.len-1; i = 0; i-) f = f*10+a.numi; c.numi = f/b; f %= b; while(len 1 & c.numlen-1 = 0) len-; c.len = len; /高精度*10 void Mul10(BigNum &a) int i, len = a.len; for(i = len; i = 1; i-) a.numi = a.numi-1; a.numi = 0; len+; /if a = 0 while(len 1 & a.numlen-1 = 0) len-; /高精度除以高精度，除的结果为c，余数为f void Div2(BigNum &a, BigNum &b, BigNum &c, BigNum &f) int i, len = a.len; memset(c.num, 0, sizeof(c.num); memset(f.num, 0, sizeof(f.num); f.len = 1; for(i = len-1;i = 0;i-) Mul10(f); /余数每次乘10 f.num0 = a.numi; /然后余数加上下一位 /利用减法替换除法 while(Comp(f, b) = 0) f = Sub(f, b); c.numi+; while(len 1 & c.numlen-1 = 0)len-; c.len = len; void print(BigNum &a) int i; for(i = a.len-1; i = 0; i-) printf(%d, a.numi); puts(); /将字符串转为大数存在BigNum结构体里面 BigNum ToNum(char *s) int i, j; BigNum a; a.len = strlen(s); for(i = 0, j = a.len-1; si != 0; i+, j-) a.numi = sj-0; return a; void Init(BigNum &a, char *s, int &tag) int i = 0, j = strlen(s); if(s0 = -) j-; i+; tag *= -1; a.len = j; for(; si != 0; i+, j-) a.numj-1 = si-0; /print(a); int main() BigNum a, b; char s1100, s2100; while(scanf(%s %s, s1, s2) != EOF) int