大整数类 问题（hdoj1002）

hdoj1002这道题大概是一月份就看到了，但是一直没有去处理。但大整数类问题在题目中比较常见，所以开始详细学习大整数类。

hdoj1002代码直接用刘汝佳的算法竞赛入门经典中的大整数BigInteger模板，运用这个模板基本能处理大部分大整数问题。

#include <bits/stdc++.h>
using namespace std;
struct BigInteger{
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    BigInteger(long long num=0) {*this = num;}//构造函数
    BigInteger operator =(long long num){     //赋值运算符
        s.clear();
        do{
            s.push_back(num % BASE);
            num /= BASE;
        }while(num > 0);
        return *this;
    }
    BigInteger operator = (const string & str){  //赋值运算符
        s.clear();
        int x, len = (str.length()-1)/WIDTH + 1;
        for(int i=0;i<len;i++){
            int end = str.length()-i*WIDTH;
            int start =max (0,end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(),"%d",&x);
            s.push_back(x);
        }
        return *this;
    }
    BigInteger operator + (const BigInteger& b) const {
        BigInteger c;
        c.s.clear();
        for(int i=0,g=0;;i++){
            if(g==0&i>=s.size()&i>=b.s.size()) break;
            int x=g;
            if(i<s.size()) x+=s[i];
            if(i<b.s.size()) x+=b.s[i];
            c.s.push_back(x%BASE);
            g=x/BASE;
        }
        return c;
    }
};
ostream& operator < (ostream &out,const BigInteger& x){
    out<x.s.back();
    for(int i=x.s.size()-2;i>=0;i--){
        char buf[20];
        sprintf(buf,"%08d",x.s[i]);
        for(int j=0;j<strlen(buf);j++) out<buf[j];
    }
    return out;
}
istream& operator > (istream &in,BigInteger& x) {
    string s;
    if(!(in>s)) return in;
    x=s;
    return in;
}
int main() {
    int n;
    int m=1;
    cin>n;
    while(n--)
  {  BigInteger x,y,p;
      cin>x>y;
      p=x+y;
      if (m != 1)
      {
          printf("\n");
      }
      printf("Case %d:\n", m++);
      cout<x<" + "<y<" = "<p<endl;

  }
    return 0;
}

** #include <bits/stdc++.h>包含C++的所有头文件 **

#include<stdio.h>
#include<string.h>
char a[1000000];   /*用两个字符数组记录两个大数 */ 
char b[1000000];
int A[1000000];     
int B[1000000];
int C[1000000];
int main()
{int n,i,j,t1,k,t2,max,x;
scanf("%d",&n);
x=0;
while(n--)
    {scanf("%s",a);
     scanf("%s",b);
     memset(A,0,sizeof(A));  /*注意每一次循环都有让数组清零 */
     memset(B,0,sizeof(B));
     memset(C,0,sizeof(C));
     t1=strlen(a);
     t2=strlen(b);
     max=t1>t2?t1:t2;
     for(j=0,k=0,i=t1-1;i>=0;i--)
         {A[j++]=a[i]-'0';   /*因为输入是从最高位到最低位输入，而计算是从最低位开始计算，所以倒着记录*/ 
          C[k++]=a[i]-'0';   /*因为最开始记录的是字符数组，所以要减去'0'字符 */
        }
     for(j=0,i=t2-1;i>=0;i--)
     B[j++]=b[i]-'0';
     for(i=0;i<max;i++)
         {A[i]=A[i]+B[i];
         if(A[i]>=10) {A[i]=A[i]-10;A[i+1]++;}  /*注意进位*/
         }
    for(i=max;(i>=0)&(A[i]==0);i--) ; /*首位如果是0的话，清0，保证最大位不是0 */ 
    if(i>=0)
        {printf("Case %d:\n",++x);
        for(j=t1-1;j>=0;j--)
        printf("%d",C[j]);
        printf(" + ");
        for(j=t2-1;j>=0;j--)
        printf("%d",B[j]);
        printf(" = ");
        for(;i>=0;i--)
        printf("%d",A[i]);
        }
    else {printf("Case %d:\n",++x);
          for(j=t1-1;j>=0;j--)
            printf("%d",C[j]);
            printf(" + ");
          for(j=t2-1;j>=0;j--)
            printf("%d",B[j]);
            printf(" = ");
              printf("0");
         }
         printf("\n");
    if(n) printf("\n");
    }
return 0;
}

第二种写法很容易理解，写起来只要注意格式就很简单了。

#include <iostream>
#include <string.h>  
using namespace std;  
void add(char a[], char b[], char tmp[]);  
int main()  
{  
    int t;  
    cin > t;  
    for(int i = 1; i <= t; i++)  
    {  
        char a[1005], b[1005], tmp[1005];  
        a[0] = b[0] = '0';  
        scanf("%s %s", &a[1], &b[1]);  
        add(a, b, tmp);  
        printf("Case %d:\n", i);  
        printf("%s + %s = ", &a[1], &b[1]);  
        if(tmp[0] != '0') printf("%c",tmp[0]);  
        printf("%s\n", &tmp[1]);  
        if(i != t)  
        cout < endl;  
    }  
    return 0;  
}  

void add(char a[], char b[], char tmp[])  
{  
    int carry = 0, t;  
    int sza = strlen(a), szb = strlen(b);  
    int sz = (sza > szb)? sza: szb;  
    tmp[sz] = '\0';  
    for(int i = sz - 1; i >= 0; i--)  
    {  
        sza--; szb--;   
        if(sza >= 0 & szb < 0)  
        {  
            t = a[sza]-48 + carry, carry = 0;  
            if(t > 9)  
                tmp[i] = t - 10 +48, carry = 1;  
            else   
                tmp[i] = t + 48;  
        }  
        if(szb >= 0 & sza < 0)  
        {  
            t = b[szb] - 48 + carry, carry = 0;  
            if(t > 9)  
                tmp[i] = t - 10 + 48, carry = 1;  
            else   
                tmp[i] = t + 48;  
        }  
        if(sza >= 0 & szb >= 0)  
        {  
            t = a[sza] - 48 + b[szb] - 48 + carry, carry = 0;  
            if(t > 9)  
                tmp[i] = t - 10 + 48, carry = 1;  
            else   
                tmp[i] = t + 48;  
        }  
    }  
}