1 #include<iostream>  2 #include<cstring>  3 #include<iomanip>  4 using namespace std;  5   6 const int MAXN=500;  7 const int DLEN=4;  8 const int WIDE=10000;  9 int A[MAXN],B[MAXN],C[MAXN]; 10 int La,Lb,Lc; 11  12 void Input(string s,int *T,int &Len) 13 { 14     int k=1,num=0; 15     memset(T,0,sizeof(&T));Len=0; 16     for(int i=s.size()-1;i>=0;i--) 17     { 18         if(k==WIDE) T[Len++]=num,num=0,k=1; 19         num+=k*(s[i]-‘0‘); 20         k*=10; 21     } 22     if(num>0) T[Len++]=num; 23 } 24  25 void Output(const int *T,int Len) 26 { 27     cout<<T[Len-1]; 28     for(int i=Len-2;i>=0;i--) 29     { 30         cout.width(DLEN); 31         cout.fill(‘0‘); 32         cout<<T[i]; 33     } 34 } 35  36 bool cmp(const int *A,const int *B,int LA,int LB) 37 { 38     if(LA!=LB) return LA<LB; 39     for(int i=LA-1;i>=0;i--) 40         if(A[i]!=B[i]) 41             return A[i]<B[i]; 42     return 0; 43 } 44  45 void Add(const int *A,const int *B,int *C,int LA,int LB,int &LC) 46 { 47     int L=max(LA,LB); 48     memset(C,0,sizeof(int)*MAXN);LC=L; 49     for(int i=0;i<L;i++) 50     { 51         C[i]+=A[i]+B[i]; 52         if(C[i]>=WIDE) 53             C[i]-=WIDE,C[i+1]++; 54     } 55     if(C[L]>0) LC++; 56 } 57  58 int Dec(const int *A,const int *B,int *C,int LA,int LB,int &LC) 59 { 60     bool flag=1; 61     int L=max(LA,LB); 62     memset(C,0,sizeof(int)*MAXN);LC=L; 63     if(cmp(A,B,LA,LB)) swap(A,B),swap(LA,LB),flag=0; 64     for(int i=0;i<L;i++) 65     { 66         C[i]+=A[i]-B[i]; 67         if(C[i]<0) 68             C[i]+=WIDE,C[i+1]--; 69     } 70     while(C[LC-1]==0) LC--; 71     return flag; 72 } 73  74 void Mult(const int *A,const int *B,int *C,int LA,int LB,int &LC) 75 { 76     memset(C,0,sizeof(int)*MAXN); 77     for(int i=0;i<LA;i++) 78         for(int j=0;j<LB;j++) 79         { 80             LC=i+j; 81             C[LC]+=A[i]*B[j]; 82             if(C[LC]>=WIDE) 83                 C[LC+1]+=C[LC]/WIDE,C[LC]%=WIDE; 84         } 85     LC=LA+LB; 86     if(C[LC-1]==0) LC--; 87 } 88  89 void Div2(int *A,int &LA) 90 { 91     for(int i=LA-1;i>=0;i--) 92     { 93         if(A[i]%2&&i>0) 94             A[i-1]+=WIDE; 95         A[i]/=2; 96     } 97     while(A[LA-1]==0) LA--; 98 } 99 void Inc(int *A,int &LA)100 {101     A[0]++;102     for(int i=0;i<LA;i++)103         if(A[i]>=WIDE)104             A[i]-=WIDE,A[i+1]++;105     if(A[LA]>0) LA++;106 }107 108 void Div(const int *A,const int *B,int *C,int LA,int LB,int &LC)109 {110     int Left[MAXN],Right[MAXN],Temp[MAXN];111     int L=1,R=LA,t,p=1;112     memset(Left,0,sizeof(int)*MAXN);113     memcpy(Right,A,sizeof(int)*MAXN);114     while(cmp(Temp,Right,t,R))115     {116         Add(Left,Right,Temp,L,R,t);117         Div2(Temp,t);118         Mult(Temp,B,C,t,LB,LC);119         if(cmp(A,C,LA,LC))120             memcpy(Right,Temp,sizeof(int)*MAXN),R=t;121         else 122             memcpy(Left,Temp,sizeof(int)*MAXN),L=t;123         memcpy(Temp,Left,sizeof(int)*MAXN),t=L;124         Inc(Temp,t);125     }126     memcpy(C,Left,sizeof(int)*MAXN);LC=L;127 }128 129 int main()130 {131     string s1,s2;132     cin>>s1>>s2;133     Input(s1,A,La);134     Input(s2,B,Lb);135     Div(A,B,C,La,Lb,Lc);136     Output(C,Lc);137     return 0;138 }