模板来自吉林大学acm模板及网络。

老师均添加了一些注释及改进。

第一个，普通的大数运算：

1 #include 
     
        2 #include 
      
         3 /*==================================================*\  4 | 普通的大数运算  5 \*==================================================*/  6 const int MAXSIZE = 200;  7 void Add(char *str1, char *str2, char *str3);  8 //str3: 和  9 void Minus(char *str1, char *str2, char *str3); 10 //要求 str1表示的数比str2的大 11 void Mul(char *str1, char *str2, char *str3); 12 //str3: 乘积 13 void Div(char *str1, char *str2, char *str3, char *str4); 14 //str3:商  str4:余数 15 //增加str4, by lyh:13/5/19 16 int main(void) 17 { 18     char str1[MAXSIZE], str2[MAXSIZE], str3[MAXSIZE], str4[MAXSIZE]; 19     while( scanf("%s %s", str1, str2) == 2 ) 20     { 21         if( strcmp(str1, "0") ) 22         { 23             memset(str3, '0', sizeof(str3)); // !!!!! 24             Add(str1, str2, str3); 25             printf("Add:%s\n", str3); 26             memset(str3, '0', sizeof(str3)); 27             Minus(str1, str2, str3); 28             printf("Minus:%s\n", str3); 29             memset(str3, '0', sizeof(str3)); 30             Mul(str1, str2, str3); 31             printf("Mul:%s\n", str3); 32             if (strcmp(str2, "0")) 33             {
   //第二个数不为0 34                 memset(str3, '0', sizeof(str3)); 35                 memset(str4, '0', sizeof(str4)); 36                 Div(str1, str2, str3,str4); 37                 printf("Div:%s\t%s\n", str3,str4); 38             } 39         } 40         else //第一个数为0的处理 41         { 42             if( strcmp(str2, "0") ) 43                 printf("%s\n-%s\n0\n0\t0\n", str2, str2); 44             else //两个数都为0的处理 45                 printf("0\n0\n0\n0\t0\n"); 46         } 47     } 48     return 0; 49 } 50 void Add(char *str1, char *str2, char *str3) 51 { 52     // str3 = str1 + str2; 53     int i, j, i1, i2, tmp, carry; 54     int len1 = strlen(str1), len2 = strlen(str2); 55     char ch; 56     i1 = len1-1; 57     i2 = len2-1; 58     j = carry = 0; 59     for( ; i1 >= 0 && i2 >= 0; ++j, --i1, --i2 ) 60     { 61         tmp = str1[i1]-'0'+str2[i2]-'0'+carry; 62         carry = tmp/10; 63         str3[j] = tmp%10+'0'; 64     } 65     while( i1 >= 0 ) 66     { 67         //处理剩余加数1 68         tmp = str1[i1--]-'0'+carry; 69         carry = tmp/10; 70         str3[j++] = tmp%10+'0'; 71     } 72     while( i2 >= 0 ) 73     { 74         //处理剩余加数2 75         tmp = str2[i2--]-'0'+carry; 76         carry = tmp/10; 77         str3[j++] = tmp%10+'0'; 78     } 79     if( carry ) //最高位进位 80         str3[j++] = carry+'0'; 81     str3[j] = '\0'; 82     for( i=0, --j; i < j; ++i, --j ) 83     { 84         // 逆序结果 85         ch = str3[i]; 86         str3[i] = str3[j]; 87         str3[j] = ch; 88     } 89 } 90 void Minus(char *str1, char *str2, char *str3) 91 { 92     // str3 = str1-str2 (str1 > str2) 93     int i, j, i1, i2, tmp, carry; 94     int len1 = strlen(str1), len2 = strlen(str2); 95     char ch; 96     i1 = len1-1; 97     i2 = len2-1; 98     j = carry = 0; 99     while( i2 >= 0 )100     {101         //处理小数str2102         tmp = str1[i1]-str2[i2]-carry;103         if( tmp < 0 )104         {105             str3[j] = tmp+10+'0';106             carry = 1;107         }108         else109         {110             str3[j] = tmp+'0';111             carry = 0;112         }113         --i1;114         --i2;115         ++j;116     }117     while( i1 >= 0 )118     {119         //处理大数str1的剩余部分120         tmp = str1[i1]-'0'-carry;121         if( tmp < 0 )122         {123             str3[j] = tmp+10+'0';124             carry = 1;125         }126         else127         {128             str3[j] = tmp+'0';129             carry = 0;130         }131         --i1;132         ++j;133     }134     --j;135     //删除数字的前导0136     while( str3[j] == '0' && j > 0 ) --j;137     str3[++j] = '\0';138     for( i=0, --j; i < j; ++i, --j )139     {140         // 逆序结果141         ch = str3[i];142         str3[i] = str3[j];143         str3[j] = ch;144     }145 }146 147 void Mul(char *str1, char *str2, char *str3)148 {149     int i, j, i1, i2, tmp, carry, jj;150     int len1 = strlen(str1), len2 = strlen(str2);151     char ch;152     jj = carry = 0;153     // jj 从最后1位向前依次处理每1位154 155     for( i1=len1-1; i1 >= 0; --i1 )156     {157         j = jj;  //j从jj开始依次处理每1位158         for( i2=len2-1; i2 >= 0; --i2, ++j )159         {160             tmp = (str3[j]-'0')+(str1[i1]-'0')*(str2[i2]-'0')+carry;161             if( tmp > 9 )162             {163                 carry = tmp/10;164                 str3[j] = tmp%10+'0';165             }166             else167             {168                 str3[j] = tmp+'0';169                 carry = 0;170             }171         }172         if( carry )173         {174             //最高位进位175             str3[j] = carry+'0';176             carry = 0;177             ++j;178         }179         ++jj;180     }181     --j;182     //去掉尾部0，即乘法结果的前导0183     while( str3[j] == '0' && j > 0 ) --j;184     str3[++j] = '\0';185     for( i=0, --j; i < j; ++i, --j )186     {187         ch = str3[i];188         str3[i] = str3[j];189         str3[j] = ch;190     }191 }192 193 void Div(char *str1, char *str2, char *str3,char *str4)194 {195     int i1, i2, i, j, jj, tag, carry, cf, c[MAXSIZE];196     //c 存商197     int len1 = strlen(str1), len2 = strlen(str2), lend;198     char d[MAXSIZE];199     //d  当前被除数,200     memset(c, 0, sizeof(c));201     memcpy(d, str1, len2);202     lend = len2;203     j = 0; //商的位数，含前导0204     for( i1=len2-1; i1 < len1; ++i1 )205     {206         //i1:商在原被除数的位置207         if( lend < len2 )208         {209             //被除数位数小于除数位数，扩充被除数位数210             d[lend] = str1[i1+1];211             c[j] = 0;212             ++j;213             ++lend;214         }215         else if( lend == len2 )216         {217             jj = 1;//被除数与除数位数相同且大于除数218             for( i=0; i < lend; ++i )219             {220                 if( d[i] > str2[i] ) break;221                 else if( d[i] < str2[i] )222                 {223                     jj = 0;224                     break;225                 }226             }227             if( jj == 0 )228             {229                 //被除数小于除数，被除数再扩充一位230                 d[lend] = str1[i1+1];231                 c[j] = 0;232                 ++j;233                 ++lend;234                 continue;235             }236         }237         if( jj==1 || lend > len2 )238         {239             //被除数大于除数，或者长度比除数多1位240             cf = jj=0;241             //cf : 是否可以进行除法242             while( d[jj] <= '0' && jj < lend ) ++jj;243             //找到被除数的第一个非0数字244             if( lend-jj > len2 )245                 cf = 1;  //被除数长度大于除数246             else if( lend-jj < len2 )247                 cf = 0; //被除数长度小于除数248             else249             {250                 //被除数长度等于除数251                 i2 = 0;252                 cf = 1;253                 for( i=jj; i < lend; ++i )254                 {255                     if( d[i] < str2[i2] )256                     {257                         //被除数小于除数258                         cf = 0;259                         break;260                     }261                     else if( d[i] > str2[i2] )262                     {263                         break;264                     }265                     ++i2;266                 }267             }//else268             while( cf )269             {270                 //被除数大于除数，求被除数/除数的商（商是1位数）271                 i2 = len2-1;272                 cf = 0;273                 for( i=lend-1; i >= lend-len2; --i )274                 {275                     //从末位向前 被除数-除数276                     d[i] = d[i]-str2[i2]+'0';277                     if( d[i] < '0' )278                     {279                         d[i] = d[i]+10;280                         carry = 1;281                         --d[i-1];282                     }283                     else carry = 0;284                     --i2;285                 }286                 ++c[j]; //累计可以的（被除数-除数）的次数，即商287                 //以下代码与上面部分重复，判断被除数是否大于除数288                 jj=0;289                 while( d[jj] <= '0' && jj < lend ) ++jj;290                 if( lend-jj > len2 ) cf = 1;291                 else if( lend-jj < len2 ) cf = 0;292                 else293                 {294                     i2 = 0;295                     cf = 1;296                     for( i=jj; i < lend; ++i )297                     {298                         if( d[i] < str2[i2] )299                         {300                             cf = 0;301                             break;302                         }303                         else if( d[i] > str2[i2] )304                         {305                             break;306                         }307                         ++i2;308                     }309                 }//else310             }//while311 312             jj = 0;313             //整理余数，得到新的被除数314             while( d[jj] <= '0' && jj < lend ) ++jj;315             for( i=0; i < lend-jj; ++i ) d[i] = d[i+jj];316             d[i] = str1[i1+1];317             lend = i+1;318             ++j;319         }//if320     }//for321     i = tag = 0;322     while( c[i] == 0 ) ++i;323     for( ; i < j; ++i, ++tag ) str3[tag] = c[i]+'0';324     str3[tag] = '\0';325 //以下内容补充 by lyh:13/5/19326 // 数组d 保存余数 327     i = tag = 0;328     while( d[i] == '0' ) ++i;329     while( d[i] != '\0' )330         str4[tag++] = d[i++];331     str4[tag] = '\0';332 //商为0时正确返回333     if(str3[0]=='\0')334     {335         str3[0]='0';336         str3[1]='\0';337     }338 //余数为0时正确返回339     if(str4[0]=='\0')340     {341         str4[0]='0';342         str4[1]='\0';343     }344 }
      
     

代码很长，中间代码有冗余，应该还可以优化。

这是一位一位的计算。

第二个，比较高效的大数运算：

1 #include 
     
        2 #include 
      
         3 /*==================================================*\  4   5  | 比较高效的大数  6  | < , <= , + , - , * , / , %(修改/的最后一行可得)  7   8 \*==================================================*/  9  10 const int base = 10000;    // (base^2) fit into int 11 const int width = 4;       // width = log base 12 const int N  = 1000;       // n * width: 可表示的最大位数 13 struct bint 14 { 15     int ln, v[N]; 16     bint (int r = 0)   // r应该是字符串！ 17     { 18         for (ln = 0; r > 0; r /= base) v[ln++] = r % base; 19     } 20     bint& operator = (const bint& r) 21     { 22         memcpy(this, &r, (r.ln + 1) * sizeof(int));// ! 23         return *this; 24     } 25 } ; 26  27 bool operator < (const bint& a, const bint& b) 28 { 29     int i; 30     if (a.ln != b.ln) return a.ln < b.ln; 31     for (i = a.ln - 1; i >= 0 && a.v[i] == b.v[i]; i--); 32     return i < 0 ? 0 : a.v[i] < b.v[i]; 33 } 34  35 bool operator <= (const bint& a, const bint& b) 36 { 37     return !(b < a); 38 } 39  40 bint operator + (const bint& a, const bint& b) 41 { 42     bint res; 43     int i, cy = 0; 44     for (i = 0; i < a.ln || i < b.ln || cy > 0; i++) 45     { 46         if (i < a.ln) cy += a.v[i]; 47         if (i < b.ln) cy += b.v[i]; 48         res.v[i] = cy % base; 49         cy /= base; 50     } 51     res.ln = i; 52     return res; 53 } 54  55 bint operator - (const bint& a, const bint& b) 56 { 57     bint res; 58     int i, cy = 0; 59     for (res.ln = a.ln, i = 0; i < res.ln; i++) 60     { 61         res.v[i] = a.v[i] - cy; 62         if (i < b.ln) res.v[i] -= b.v[i]; 63         if (res.v[i] < 0) cy = 1, res.v[i] += base; 64         else cy = 0; 65     } 66         //去掉结果的前导0，同时修正长度 67     while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--; 68     return res; 69 } 70  71 bint operator * (const bint& a, const bint& b) 72 { 73     bint res; 74     res.ln = 0; 75     if (0 == b.ln) 76     { 77         res.v[0] = 0; 78         return res; 79     } 80     int i, j, cy; 81     for (i = 0; i < a.ln; i++) 82     { 83         for (j=cy=0; j < b.ln || cy > 0; j++, cy/= base) 84         { 85             if (j < b.ln) cy += a.v[i] * b.v[j]; 86             if (i + j < res.ln) cy += res.v[i + j]; 87             if (i + j >= res.ln) res.v[res.ln++] = cy % base; 88             else res.v[i + j] = cy % base; 89         } 90     } 91     return res; 92 } 93 bint operator / (const bint& a, const bint& b) 94 {    // ! b != 0 95     bint tmp, mod, res; 96     int i, lf, rg, mid; 97     mod.v[0] = mod.ln = 0; 98     for (i = a.ln - 1; i >= 0; i--) 99     {100         mod = mod * base + a.v[i];101                 //试商，找到最大的商102         for (lf = 0, rg = base -1; lf < rg; )103         {104             mid = (lf + rg + 1) / 2;105             if (b * mid <= mod) lf = mid;106             else rg = mid - 1;107         }108         res.v[i] = lf; //商109         mod = mod - b * lf; //余数110     }111     res.ln = a.ln;112     while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;113     return res;          // return mod 就是%运算114 }115 int digits(bint& a)          // 返回位数116 {117     if (a.ln == 0) return 0;118     int l = ( a.ln - 1 ) * 4;119         //最高位可能不足4位，需要逐位确定120     for (int t = a.v[a.ln - 1]; t; ++l, t/=10) ;121     return l;122 }123 bool read(bint& b, char buf[])  // 读取失败返回0124 {125     if (1 != scanf("%s", buf)) return 0;126     int w, u, ln = strlen(buf);127     memset(&b, 0, sizeof(bint));128     if ('0' == buf[0] && 0 == buf[1]) return 1;129     for (w = 1, u = 0; ln; )130     {131         u += (buf[--ln] - '0') * w;132         if (w * 10 == base)133         {134             b.v[b.ln++] = u;135             u = 0;136             w = 1;137         }138         else w *= 10;139     }140     if (w != 1) b.v[b.ln++] = u;141     return 1;142 }143 144 void write(const bint& v)145 {146     int i;147     printf("%d", v.ln == 0 ? 0 : v.v[v.ln - 1]);148     for (i = v.ln - 2; i >= 0; i--)149         printf("%04d", v.v[i]);  // ! 4 == width150     printf("\n");151 }152 153 int main(){154     const int MAXSIZE = 200;155     char str1[MAXSIZE];156     bint b1,b2,b3,b4;157     read(b1, str1);158     read(b2, str1);159     b3=b1+b2;160     write(b3);161     b3=b1-b2;162     write(b3);163     b3=b1*b2;164     write(b3);165     b3=b1/b2;166     write(b3);167 168     return 0;169 }
      
     

　　与第一个不同的是，每四位每四位的计算，计算的时候不是用字符串计算，而是直接用原来的除法运算，因为原来的一定要快，大数运算的时候能用原来的加减乘除运算就尽量用原来的。为什么划出四位来，因为9999*9999约等于10^8，而int型数据最高不过能储存10^9位数，当然你也可以用64数运算（longlong）。

　　另外每四位除法运算的时候是用二分法试商，小学老师教我们的时候能凑出来就凑出来，因为基本一眼就看出来了，而正规的做法应该是不断二分试商，直到上界和下界交叉或等于的时候，那个结果就是正确结果。

 第三个，老师提了一下，思路和第二个差不多，只不过更加细化，加了一些东西，老师说“感觉上更快一些”，名字是《捡来的一个大数模板》，来自网络：

1 //http://www.cnblogs.com/cj695/archive/2012/07/28/2613678.html  2 #include 
     
            3 #include 
      
             4 using namespace std;      5       6 #define DIGIT   4      //四位隔开,即万进制      7 #define DEPTH   10000        //万进制      8 #define MAX     251    //题目最大位数/4，要不大直接设为最大位数也行   9 typedef int bignum_t[MAX+1];    //a[0] 用作临时变量 10       11 /************************************************************************/    12 /* 读取操作数，对操作数进行处理存储在数组里                             */    13 /************************************************************************/    14 int read(bignum_t a,istream&is=cin)     15 {     16     char buf[MAX*DIGIT+1],ch ;     17     int i,j ;     18     memset((void*)a,0,sizeof(bignum_t));     19     if(!(is>>buf))return 0 ;     20 //字符串buf逆序，a[0] 初始化为字符串长度 21     for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)     22     ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;     23 //把数据补足为4(DIGIT)位 ,前面+0 24     for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j
       
        1;a[0]--);     31     return 1 ;     32 }     33       34 void write(const bignum_t a,ostream&os=cout)     35 {     36     int i,j ;     37 //逆序输出数组 a[],高位在后 38     for(os<
        
         =DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);     66 //调用其他重载 67     return comp(a,c);     68 }     69       70 int comp(const bignum_t a,const int c,const int d,const bignum_t b)     71 {     72 // 测试 a * c 是否大于b ，d 表示  73     int i,t=0,O=-DEPTH*2 ;     74     if(b[0]-a[0]
         
          d;i--)     77     {     78         t=t*DEPTH+a[i-d]*c-b[i];     79         if(t>0)return 1 ;     80         if(t
          
           0)return 1 ; 86 if(t
           
            0 ; 89 } 90 /************************************************************************/ 91 /* 大数与大数相加 */ 92 /************************************************************************/ 93 void add(bignum_t a,const bignum_t b) 94 { 95 int i ; 96 for(i=1;i<=b[0];i++) 97 if((a[i]+=b[i])>=DEPTH) 98 a[i]-=DEPTH,a[i+1]++; 99 if(b[0]>=a[0]) 100 a[0]=b[0]; 101 else 102 for(;a[i]>=DEPTH&&i
            
             0); 104 } 105 /************************************************************************/ 106 /* 大数与小数相加 */ 107 /************************************************************************/ 108 void add(bignum_t a,const int b) 109 { 110 int i=1 ; 111 for(a[1]+=b;a[i]>=DEPTH&&i
             
              =DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++); 113 } 114 /************************************************************************/ 115 /* 大数相减(被减数>=减数) */ 116 /************************************************************************/ 117 void sub(bignum_t a,const bignum_t b) 118 { 119 int i ; 120 for(i=1;i<=b[0];i++) 121 if((a[i]-=b[i])<0) 122 a[i+1]--,a[i]+=DEPTH ; 123 for(;a[i]<0;a[i]+=DEPTH,i++,a[i]--); 124 for(;!a[a[0]]&&a[0]>1;a[0]--); 125 } 126 /************************************************************************/ 127 /* 大数减去小数(被减数>=减数) */ 128 /************************************************************************/ 129 void sub(bignum_t a,const int b) 130 { 131 int i=1 ; 132 for(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++); 133 for(;!a[a[0]]&&a[0]>1;a[0]--); 134 } 135 136 void sub(bignum_t a,const bignum_t b,const int c,const int d) 137 { 138 int i,O=b[0]+d ; 139 for(i=1+d;i<=O;i++) 140 if((a[i]-=b[i-d]*c)<0) 141 a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ; 142 for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++); 143 for(;!a[a[0]]&&a[0]>1;a[0]--); 144 } 145 /************************************************************************/ 146 /* 大数相乘，读入被乘数a，乘数b，结果保存在c[] */ 147 /************************************************************************/ 148 void mul(bignum_t c,const bignum_t a,const bignum_t b) 149 { 150 int i,j ; 151 memset((void*)c,0,sizeof(bignum_t)); 152 for(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++) 153 for(j=1;j<=b[0];j++) 154 if((c[i+j-1]+=a[i]*b[j])>=DEPTH) 155 c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ; 156 for(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--); 157 } 158 /************************************************************************/ 159 /* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数 */ 160 /************************************************************************/ 161 void mul(bignum_t a,const int b) 162 { 163 int i ; 164 for(a[1]*=b,i=2;i<=a[0];i++) 165 { 166 a[i]*=b ; 167 if(a[i-1]>=DEPTH) 168 a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ; 169 } 170 for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++); 171 for(;!a[a[0]]&&a[0]>1;a[0]--); 172 } 173 174 void mul(bignum_t b,const bignum_t a,const int c,const int d) 175 { 176 int i ; 177 memset((void*)b,0,sizeof(bignum_t)); 178 for(b[0]=a[0]+d,i=d+1;i<=b[0];i++) 179 if((b[i]+=a[i-d]*c)>=DEPTH) 180 b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ; 181 for(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH); 182 for(;!b[b[0]]&&b[0]>1;b[0]--); 183 } 184 /**************************************************************************/ 185 /* 大数相除,读入被除数a，除数b，结果保存在c[]数组 */ 186 /* 需要comp()函数 */ 187 /**************************************************************************/ 188 void div(bignum_t c,bignum_t a,const bignum_t b) 189 { 190 int h,l,m,i ; 191 memset((void*)c,0,sizeof(bignum_t)); 192 c[0]=(b[0]
              
               >1;h>l;m=(h+l+1)>>1) 195 if(comp(b,m,i-1,a))h=m-1 ; 196 else l=m ; 197 for(;!c[c[0]]&&c[0]>1;c[0]--); 198 c[0]=c[0]>1?c[0]:1 ; 199 } 200 201 void div(bignum_t a,const int b,int&c) 202 { 203 int i ; 204 for(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--); 205 for(;!a[a[0]]&&a[0]>1;a[0]--); 206 } 207 /************************************************************************/ 208 /* 大数平方根，读入大数a，结果保存在b[]数组里 */ 209 /* 需要comp()函数 */ 210 /************************************************************************/ 211 void sqrt(bignum_t b,bignum_t a) 212 { 213 int h,l,m,i ; 214 memset((void*)b,0,sizeof(bignum_t)); 215 for(i=b[0]=(a[0]+1)>>1;i;sub(a,b,m,i-1),b[i]+=m,i--) 216 for(h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1) 217 if(comp(b,m,i-1,a))h=m-1 ; 218 else l=m ; 219 for(;!b[b[0]]&&b[0]>1;b[0]--); 220 for(i=1;i<=b[0];b[i++]>>=1); 221 } 222 /************************************************************************/ 223 /* 返回大数的长度 */ 224 /************************************************************************/ 225 int length(const bignum_t a) 226 { 227 int t,ret ; 228 for(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++); 229 return ret>0?ret:1 ; 230 } 231 /************************************************************************/ 232 /* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数 */ 233 /************************************************************************/ 234 int digit(const bignum_t a,const int b) 235 { 236 int i,ret ; 237 for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--); 238 return ret%10 ; 239 } 240 /************************************************************************/ 241 /* 返回大数末尾0的个数 */ 242 /************************************************************************/ 243 int zeronum(const bignum_t a) 244 { 245 int ret,t ; 246 for(ret=0;!a[ret+1];ret++); 247 for(t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++); 248 return ret ; 249 } 250 251 void comp(int*a,const int l,const int h,const int d) 252 { 253 int i,j,t ; 254 for(i=l;i<=h;i++) 255 for(t=i,j=2;t>1;j++) 256 while(!(t%j)) 257 a[j]+=d,t/=j ; 258 } 259 260 void convert(int*a,const int h,bignum_t b) 261 { 262 int i,j,t=1 ; 263 memset(b,0,sizeof(bignum_t)); 264 for(b[0]=b[1]=1,i=2;i<=h;i++) 265 if(a[i]) 266 for(j=a[i];j;t*=i,j--) 267 if(t*i>DEPTH) 268 mul(b,t),t=1 ; 269 mul(b,t); 270 } 271 /************************************************************************/ 272 /* 组合数 */ 273 /************************************************************************/ 274 void combination(bignum_t a,int m,int n) 275 { 276 int*t=new int[m+1]; 277 memset((void*)t,0,sizeof(int)*(m+1)); 278 comp(t,n+1,m,1); 279 comp(t,2,m-n,-1); 280 convert(t,m,a); 281 delete[]t ; 282 } 283 /************************************************************************/ 284 /* 排列数 */ 285 /************************************************************************/ 286 void permutation(bignum_t a,int m,int n) 287 { 288 int i,t=1 ; 289 memset(a,0,sizeof(bignum_t)); 290 a[0]=a[1]=1 ; 291 for(i=m-n+1;i<=m;t*=i++) 292 if(t*i>DEPTH) 293 mul(a,t),t=1 ; 294 mul(a,t); 295 } 296 297 #define SGN(x) ((x)>0?1:((x)<0?-1:0)) 298 #define ABS(x) ((x)>0?(x):-(x)) 299 300 int read(bignum_t a,int&sgn,istream&is=cin) 301 { 302 char str[MAX*DIGIT+2],ch,*buf ; 303 int i,j ; 304 memset((void*)a,0,sizeof(bignum_t)); 305 if(!(is>>str))return 0 ; 306 buf=str,sgn=1 ; 307 if(*buf=='-')sgn=-1,buf++; 308 for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--) 309 ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ; 310 for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j
               
                1;a[0]--); 315 if(a[0]==1&&!a[1])sgn=0 ; 316 return 1 ; 317 } 318 struct bignum 319 { 320 bignum_t num ; 321 int sgn ; 322 public : 323 inline bignum() 324 { 325 memset(num,0,sizeof(bignum_t)); 326 num[0]=1 ; 327 sgn=0 ; 328 } 329 inline int operator!() 330 { 331 return num[0]==1&&!num[1]; 332 } 333 inline bignum&operator=(const bignum&a) 334 { 335 memcpy(num,a.num,sizeof(bignum_t)); 336 sgn=a.sgn ; 337 return*this ; 338 } 339 inline bignum&operator=(const int a) 340 { 341 memset(num,0,sizeof(bignum_t)); 342 num[0]=1 ; 343 sgn=SGN (a); 344 add(num,sgn*a); 345 return*this ; 346 } 347 ; 348 inline bignum&operator+=(const bignum&a) 349 { 350 if(sgn==a.sgn)add(num,a.num); 351 else if 352 (sgn&&a.sgn) 353 { 354 int ret=comp(num,a.num); 355 if(ret>0)sub(num,a.num); 356 else if(ret<0) 357 { 358 bignum_t t ; 359 memcpy(t,num,sizeof(bignum_t)); 360 memcpy(num,a.num,sizeof(bignum_t)); 361 sub (num,t); 362 sgn=a.sgn ; 363 } 364 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ; 365 } 366 else if(!sgn) 367 memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ; 368 return*this ; 369 } 370 inline bignum&operator+=(const int a) 371 { 372 if(sgn*a>0)add(num,ABS(a)); 373 else if(sgn&&a) 374 { 375 int ret=comp(num,ABS(a)); 376 if(ret>0)sub(num,ABS(a)); 377 else if(ret<0) 378 { 379 bignum_t t ; 380 memcpy(t,num,sizeof(bignum_t)); 381 memset(num,0,sizeof(bignum_t)); 382 num[0]=1 ; 383 add(num,ABS (a)); 384 sgn=-sgn ; 385 sub(num,t); 386 } 387 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ; 388 } 389 else if 390 (!sgn)sgn=SGN(a),add(num,ABS(a)); 391 return*this ; 392 } 393 inline bignum operator+(const bignum&a) 394 { 395 bignum ret ; 396 memcpy(ret.num,num,sizeof (bignum_t)); 397 ret.sgn=sgn ; 398 ret+=a ; 399 return ret ; 400 } 401 inline bignum operator+(const int a) 402 { 403 bignum ret ; 404 memcpy(ret.num,num,sizeof (bignum_t)); 405 ret.sgn=sgn ; 406 ret+=a ; 407 return ret ; 408 } 409 inline bignum&operator-=(const bignum&a) 410 { 411 if(sgn*a.sgn<0)add(num,a.num); 412 else if 413 (sgn&&a.sgn) 414 { 415 int ret=comp(num,a.num); 416 if(ret>0)sub(num,a.num); 417 else if(ret<0) 418 { 419 bignum_t t ; 420 memcpy(t,num,sizeof(bignum_t)); 421 memcpy(num,a.num,sizeof(bignum_t)); 422 sub(num,t); 423 sgn=-sgn ; 424 } 425 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ; 426 } 427 else if(!sgn)add (num,a.num),sgn=-a.sgn ; 428 return*this ; 429 } 430 inline bignum&operator-=(const int a) 431 { 432 if(sgn*a<0)add(num,ABS(a)); 433 else if(sgn&&a) 434 { 435 int ret=comp(num,ABS(a)); 436 if(ret>0)sub(num,ABS(a)); 437 else if(ret<0) 438 { 439 bignum_t t ; 440 memcpy(t,num,sizeof(bignum_t)); 441 memset(num,0,sizeof(bignum_t)); 442 num[0]=1 ; 443 add(num,ABS(a)); 444 sub(num,t); 445 sgn=-sgn ; 446 } 447 else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ; 448 } 449 else if 450 (!sgn)sgn=-SGN(a),add(num,ABS(a)); 451 return*this ; 452 } 453 inline bignum operator-(const bignum&a) 454 { 455 bignum ret ; 456 memcpy(ret.num,num,sizeof(bignum_t)); 457 ret.sgn=sgn ; 458 ret-=a ; 459 return ret ; 460 } 461 inline bignum operator-(const int a) 462 { 463 bignum ret ; 464 memcpy(ret.num,num,sizeof(bignum_t)); 465 ret.sgn=sgn ; 466 ret-=a ; 467 return ret ; 468 } 469 inline bignum&operator*=(const bignum&a) 470 { 471 bignum_t t ; 472 mul(t,num,a.num); 473 memcpy(num,t,sizeof(bignum_t)); 474 sgn*=a.sgn ; 475 return*this ; 476 } 477 inline bignum&operator*=(const int a) 478 { 479 mul(num,ABS(a)); 480 sgn*=SGN(a); 481 return*this ; 482 } 483 inline bignum operator*(const bignum&a) 484 { 485 bignum ret ; 486 mul(ret.num,num,a.num); 487 ret.sgn=sgn*a.sgn ; 488 return ret ; 489 } 490 inline bignum operator*(const int a) 491 { 492 bignum ret ; 493 memcpy(ret.num,num,sizeof (bignum_t)); 494 mul(ret.num,ABS(a)); 495 ret.sgn=sgn*SGN(a); 496 return ret ; 497 } 498 inline bignum&operator/=(const bignum&a) 499 { 500 bignum_t t ; 501 div(t,num,a.num); 502 memcpy (num,t,sizeof(bignum_t)); 503 sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ; 504 return*this ; 505 } 506 inline bignum&operator/=(const int a) 507 { 508 int t ; 509 div(num,ABS(a),t); 510 sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a); 511 return*this ; 512 } 513 inline bignum operator/(const bignum&a) 514 { 515 bignum ret ; 516 bignum_t t ; 517 memcpy(t,num,sizeof(bignum_t)); 518 div(ret.num,t,a.num); 519 ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ; 520 return ret ; 521 } 522 inline bignum operator/(const int a) 523 { 524 bignum ret ; 525 int t ; 526 memcpy(ret.num,num,sizeof(bignum_t)); 527 div(ret.num,ABS(a),t); 528 ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a); 529 return ret ; 530 } 531 inline bignum&operator%=(const bignum&a) 532 { 533 bignum_t t ; 534 div(t,num,a.num); 535 if(num[0]==1&&!num[1])sgn=0 ; 536 return*this ; 537 } 538 inline int operator%=(const int a) 539 { 540 int t ; 541 div(num,ABS(a),t); 542 memset(num,0,sizeof (bignum_t)); 543 num[0]=1 ; 544 add(num,t); 545 return t ; 546 } 547 inline bignum operator%(const bignum&a) 548 { 549 bignum ret ; 550 bignum_t t ; 551 memcpy(ret.num,num,sizeof(bignum_t)); 552 div(t,ret.num,a.num); 553 ret.sgn=(ret.num[0]==1&&!ret.num [1])?0:sgn ; 554 return ret ; 555 } 556 inline int operator%(const int a) 557 { 558 bignum ret ; 559 int t ; 560 memcpy(ret.num,num,sizeof(bignum_t)); 561 div(ret.num,ABS(a),t); 562 memset(ret.num,0,sizeof(bignum_t)); 563 ret.num[0]=1 ; 564 add(ret.num,t); 565 return t ; 566 } 567 inline bignum&operator++() 568 { 569 *this+=1 ; 570 return*this ; 571 } 572 inline bignum&operator--() 573 { 574 *this-=1 ; 575 return*this ; 576 } 577 ; 578 inline int operator>(const bignum&a) 579 { 580 return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0); 581 } 582 inline int operator>(const int a) 583 { 584 return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0); 585 } 586 inline int operator>=(const bignum&a) 587 { 588 return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0); 589 } 590 inline int operator>=(const int a) 591 { 592 return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0); 593 } 594 inline int operator<(const bignum&a) 595 { 596 return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0); 597 } 598 inline int operator<(const int a) 599 { 600 return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0); 601 } 602 inline int operator<=(const bignum&a) 603 { 604 return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0); 605 } 606 inline int operator<=(const int a) 607 { 608 return sgn<0?(a<0?comp(num,-a)>=0:1): 609 (sgn>0?(a>0?comp(num,a)<=0:0):a>=0); 610 } 611 inline int operator==(const bignum&a) 612 { 613 return(sgn==a.sgn)?!comp(num,a.num):0 ; 614 } 615 inline int operator==(const int a) 616 { 617 return(sgn*a>=0)?!comp(num,ABS(a)):0 ; 618 } 619 inline int operator!=(const bignum&a) 620 { 621 return(sgn==a.sgn)?comp(num,a.num):1 ; 622 } 623 inline int operator!=(const int a) 624 { 625 return(sgn*a>=0)?comp(num,ABS(a)):1 ; 626 } 627 inline int operator[](const int a) 628 { 629 return digit(num,a); 630 } 631 friend inline istream&operator>>(istream&is,bignum&a) 632 { 633 read(a.num,a.sgn,is); 634 return is ; 635 } 636 friend inline ostream&operator<<(ostream&os,const bignum&a) 637 { 638 if(a.sgn<0) 639 os<<'-' ; 640 write(a.num,os); 641 return os ; 642 } 643 friend inline bignum sqrt(const bignum&a) 644 { 645 bignum ret ; 646 bignum_t t ; 647 memcpy(t,a.num,sizeof(bignum_t)); 648 sqrt(ret.num,t); 649 ret.sgn=ret.num[0]!=1||ret.num[1]; 650 return ret ; 651 } 652 friend inline bignum sqrt(const bignum&a,bignum&b) 653 { 654 bignum ret ; 655 memcpy(b.num,a.num,sizeof(bignum_t)); 656 sqrt(ret.num,b.num); 657 ret.sgn=ret.num[0]!=1||ret.num[1]; 658 b.sgn=b.num[0]!=1||ret.num[1]; 659 return ret ; 660 } 661 inline int length() 662 { 663 return :: length(num); 664 } 665 inline int zeronum() 666 { 667 return :: zeronum(num); 668 } 669 inline bignum C(const int m,const int n) 670 { 671 combination(num,m,n); 672 sgn=1 ; 673 return*this ; 674 } 675 inline bignum P(const int m,const int n) 676 { 677 permutation(num,m,n); 678 sgn=1 ; 679 return*this ; 680 } 681 }; 682 int main() 683 { 684 bignum a,b,c; 685 cin>>a>>b; 686 cout<<"加法:"<
                
                 <