CRJ巨佬的gjd算法模板

数组高精度

定义：

 bignum(){
    flag = 1;  len = 0;
  }

赋值运算：

void operator =(long long a) {
  int i=0;
  while(a!=0) {
     N[i]=a%10;
     a/=10;
     i++;
  }
  len=i;
}
  
void operator = (string g) {
  for(int i=0;i<g.size();i++)    N[i]=g[g.size()-1-i]-48;
  len=g.size();
}

输出：

void pt()
{
    if(flag==0) printf("-");
    for(int i=len;i>=0;i--) printf("%d",N[i]);
}

三则运算：

    friend bignum operator + (bignum f,bignum g)
    {
        bignum ans;
        ans.len=max(f.len,g.len)+1;
        int tp=0;
        for(int i=0;i<=ans.len;i++)
        {
            ans.N[i]=f.N[i]+g.N[i]+tp;
            tp=ans.N[i]/10;
            ans.N[i]%=10;
        }
        int i=ans.len;
        while(ans.N[i]==0&&i>0)
        {
            ans.len--;
            i--;    
        } 
        return ans;
    }
    
    friend bignum operator * (bignum f,bignum g)
    {
        bignum ans;
        ans.len=f.len+g.len;
        int tp=0;
        for(int i=0;i<f.len;i++)
        {
            for(int j=0;j<g.len;j++)
            {
                ans.N[i+j]+=f.N[i]*g.N[j];
                ans.N[i+j+1]+=ans.N[i+j]/10;
                ans.N[i+j]%=10;
            }
        }
        int i=ans.len;
        while(ans.N[i]==0&&i>0)
        {
            ans.len--;
            i--;    
        } 
        return ans;
    }
    
    friend bignum operator - (bignum f,bignum g)
    {
        bignum ans;
        if(f<g) 
        {
            swap(f,g);
            ans.flag=0;
        }
        
        ans.len=max(f.len,g.len);
        for(int i=0;i<f.len;i++)
        {
            ans.N[i]=f.N[i]-g.N[i];
            if(ans.N[i]<0) 
            {
                f.N[i+1]--;
                ans.N[i]+=10;    
            }
        }
        int i=ans.len;
        while(ans.N[i]==0&&i>0)
        {
            ans.len--;
            i--;    
        } 
        return ans;
    }

比较运算：

    friend bool operator < (bignum f,bignum g)
    {
        if(f.len<g.len) return true;
        else if(f.len==g.len)
        {
            bool flg=1;
            for(int i=0;i<g.len;i++)if(f.N[i]<g.N[i])    return true;
            return false;
        } else return false;
    }

完整代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 #define LL long long
 7 
 8 struct bignum {
 9   int N[1000],len,flag;
10   
11   bignum(){
12     flag = 1;  len = 0;
13   }
14   
15   void operator = (LL a) {
16     int i = 0;
17     while(a != 0) {
18       N[i++] = a % 10;
19       a /= 10;
20     }
21     len = i;
22   }
23 
24   void operator = (string a) {
25     int lena = a.length();
26     for(int i = 0;i < lena;i++) N[i] = a[lena-1-i]-'0';
27     len = lena;
28   }
29  
30   friend bignum operator + (bignum a,bignum b) {
31     bignum ret;
32     ret.len = max(a.len,b.len) + 1;
33     int tp = 0;
34     for(int i = 0;i <= ret.len;i++) {
35       ret.N[i] = a.N[i] + b.N[i] + tp;
36       tp = ret.N[i] / 10;
37       ret.N[i] %= 10;
38     }
39     int i = ret.len;
40     while(ret.N[i] == 0 && i > 0) {
41       ret.len--; i--;
42     }
43     return ret;
44   }
45 
46   friend bignum operator * (bignum a,bignum b) {
47     bignum ret;
48     ret.len = a.len + b.len;
49     for(int i = 0;i < a.len;i++) {
50       for(int j = 0;j < b.len;j++) {
51         ret.N[i+j] += a.N[i]*b.N[j];
52         ret.N[i+j+1] += ret.N[i+j]/10;
53         ret.N[i+j] %= 10;
54       }
55     }
56     int i = ret.len;
57     while(ret.N[i] == 0 && i > 0) {
58       ret.len--;  i--;
59     }
60     return ret;
61   }
62   
63   friend bignum operator - (bignum a, bignum b) {
64     bignum ret;
65     if(a < b) swap(a,b),ret.flag = 0;
66     ret.len = max(a.len, b.len);
67     for(int i = 0;i < a.len;i++) {
68       ret.N[i] = a.N[i] - b.N[i];
69       if(ret.N[i] < 0) a.N[i+1]--, ret.N[i] += 10;
70     }
71     int i = ret.len;
72     while(ret.N[i] == 0 && i > 0) {
73       ret.len--; i--;
74     }
75     return ret;
76   }
77  
78   friend bool operator < (bignum a,bignum b) {
79      if(a.len < b.len) return true;
80      else if(a.len == b.len) {
81        for(int i = 0;i < b.len;i++) if(a.N[i] < b.N[i]) return true;
82        return false;
83      } else return false;
84    }
85  
86   void pt() {
87     if(flag == 0) printf("-");
88     for(int i = len;i >= 0;i--) printf("%d",N[i]);
89   }
90 };
91 
92 int main() {
93   bignum a,b;
94   string aa,bb;
95   cin >> aa >> bb;
96   a = aa; b = bb;
97   (a * b).pt();
98   return 0;
99 }