参考： Mr. He的高精度算法讲稿
高精度的存储结构：
#define maxn 5005 struct bign //高精度结构体 { int len,z[maxn]; bign() //构造函数，初始化高精度变量的值为 0 { len=1; //0是一位数 memset(z,0,sizeof(z)); //各位数字为0; } }; bign a,b; //定义了一个高精度变量实现高精度运算的 13 大函数列表如下：
1、bign fuzhi(char *s) //赋值运算：把一个数字字符串赋值给高精度变量
bign fuzhi(char *s) //把一个字符串赋值给高精度 { bign a; a.len=strlen(s); for(int i=0;i<a.len;i++) a.z[a.len-1-i]=s[i]-48; while(a.len>1 && a.z[a.len-1]==0) a.len--; //去掉高位0 return a; }2、bign fuzhi(int num) //赋值运算：把一个整数赋给高精度变量
bign fuzhi(int num) //把一个整数赋值给高精度 { char s[25]; sprintf(s,"%d",num); return fuzhi(s); }3、void bign_in(bign &a) //高精度输入
void bign_in(bign &a) //注意：别名变量 { scanf("%s",s); a=fuzhi(s); //把子符串赋值给高精度变量 }4、void bign_out(bign &a) //高精度输出
void bign_out(bign a) { for(int i=a.len-1;i>=0;i--) printf("%d",a.z[i]); printf("\n"); }5、bool xiaoyu(bign a,bign b) //比较运算：a < b为true
bool xiaoyu(bign a,bign b) { if(a.len!=b.len) return a.len<b.len; for(int i=a.len-1;i>=0;i--) if(a.z[i]!=b.z[i]) return a.z[i]<b.z[i]; return false; }就利用这个函数，可以判断其他关系： ◆a>b 的判断：b 小于 a
if(xiaoyu(b,a)) ……◆a<=b 的判断：b 不小于 a
if(!xiaoyu(b,a)) ……◆a>=b 的判断：a 不小于 b
if(!xiaoyu(a,b)) ……◆a==b 的判断：a 大于等于 b 且 b 大于等于 a
if(!xiaoyu(a,b) && !xiaoyu(b,a)) ……◆a!=b 的判断：a 大于 b 或 b 大于 a
if(xiaoyu(a,b) || xiaoyu(b,a)) ……6、bign jia(bign a,bign b) //加法运算：高精度加高精度：a+b
bign jia(bign a,bign b) //高精度加法 a+b { bign c; c.len=max(a.len,b.len); //和的位数，max()在<algorithm>中 for(int i=0;i<c.len;i++) //逐位相加 c.z[i]=a.z[i]+b.z[i]; for(int i=0;i<c.len;i++) //处理进位 if(c.z[i]>=10) { c.z[i+1]++; c.z[i]=c.z[i]-10; } if(c.z[c.len]>0) c.len++; //如过最高位有进位，则和的位数增加 return c; }7、bign jian(bign a,bign b) //减法运算：高精度减高精度：a-b
bign jian(bign a,bign b) //高精度减法 a-b { bign c; c.len=max(a.len,b.len); //差的位数，max()函数在<algorithm>中 for(int i=0;i<c.len;i++) //逐位相减 c.z[i]=a.z[i]-b.z[i]; for(int i=0;i<c.len;i++) //处理借位 if(c.z[i]<0) { c.z[i+1]--; c.z[i]=c.z[i]+10; } while(c.len>1 && c.z[c.len-1]==0) c.len--; //去掉整数的前导 0 return c; }8、bign cheng(bign a,int b) //乘法运算：高精度乘int：a*b
bign cheng(bign a,int b) { bign c; c.len=a.len+11; for(int i=0;i<a.len;i++) c.z[i]=a.z[i]*b; for(int i=0;i<c.len;i++) if(c.z[i]>=10) { c.z[i+1]=c.z[i+1]+c.z[i]/10; c.z[i]=c.z[i]%10; } while(c.len>1 && c.z[c.len-1]==0) c.len--; return c; }9、bign cheng(bign a,bign b) //乘法运算：高精度乘高精度：a*b
bign cheng(bign a,bign b) //高精度乘法 a*b { bign c; c.len=a.len+b.len; for(int i=0;i<a.len;i++) //a的第i位乘以 b 的第j位，得到c的第 i+j 位 for(int j=0;j<b.len;j++) c.z[i+j]=c.z[i+j]+a.z[i]*b.z[j]; //边乘边加 for(int i=0;i<c.len;i++) //处理进位 if(c.z[i]>=10) { c.z[i+1]=c.z[i+1]+c.z[i]/10; c.z[i]=c.z[i]%10; } while(c.len>1 && c.z[c.len-1]==0) c.len--; return c; }10、bign chu(bign a,int b) //除法运算：高精度除以int：a/b
bign chu(bign a,int b) //高精度除整数 { bign c; int d=0; c.len=a.len; for(int i=a.len-1;i>=0;i--) { d=d*10+a.z[i]; c.z[i]=d/b; d=d%b; } while(c.len>1 && c.z[c.len-1]==0) c.len--; return c; }11、bign chu(bign a,bign b) //除法运算：高精度除以高精度：a/b
bign chu(bign a,bign b) //高精度除法a/b { bign c,d,ten; c.len=a.len; ten=fuzhi(10); //高精度的10 for(int i=a.len-1;i>=0;i--) { d=cheng(d,ten); d.z[0]=a.z[i]; while(!xiaoyu(d,b)) //d>=b { c.z[i]++; d=jian(d,b); } } while(c.len>1 && c.z[c.len-1]==0) c.len--; return c; }12、int yu(bign a,int b) //取余运算：高精度除以int 的余数：a%b
int yu(bign a,int b) //高精度除int取余 { int d=0; for(int i=a.len-1;i>=0;i--) { d=d*10+a.z[i]; d=d%b; } return d; }13、bign yu(bign a,bign b) //取余运算：高精度除以高精度的余数：a%b
bign yu(bign a,bign b) //高精度取余 a%b { bign d,ten; ten=fuzhi(10); for(int i=a.len-1;i>=0;i--) { d=cheng(d,ten); d.z[0]=a.z[i]; while(!xiaoyu(d,b)) { d=jian(d,b); } } while(d.len>1 && d.z[d.len-1]==0) d.len--; return d; }