9.7 函数整合

 

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #define ll long long
  5 #define MAXN 400000
  6 
  7 using namespace std;
  8 
  9 char sa[MAXN],sb[MAXN];
 10 int a[MAXN],b[MAXN],c[MAXN],d;
 11 
 12 template<typename type>
 13 inline void get(char sa[],type a[],bool mode)//读入一个数，按位存到a数组中，mode为0正序存，为1倒序存 
 14 {
 15     memset(a,0,sizeof(a));
 16     cin>>sa;
 17     int len=strlen(sa);
 18     if(mode) for(int i(1);i<=len;i++) a[i]=sa[len-i]^48;
 19     else for(int i(1);i<=len;i++) a[i]=sa[i-1]^48; 
 20 }
 21 
 22 template<typename type>
 23 inline void put(int len,type c[],bool mode)//按位输出一个长度为len的数组，mode为0正序输出，为1倒序输出
 24 {
 25     if(mode) for(int i(len);i>0;i--) cout<<c[i];
 26     else for(int i(1);i<=len;i++) cout<<c[i];
 27     puts("");
 28 }
 29 
 30 //高精度加法 
 31 template<typename type>
 32 inline void add(char sa[],char sb[],type a[],type b[],type c[])
 33 {
 34     memset(c,0,sizeof(c));
 35     get(sa,a,1);
 36     get(sb,b,1);
 37     int lena=strlen(sa),lenb=strlen(sb),lenc(0),carry(0);//carry存进位 
 38     while(lenc<=lena||lenc<=lenb)
 39     {
 40         c[lenc]=a[lenc]+b[lenc]+carry;
 41         carry=c[lenc]/10;
 42         c[lenc]%=10;
 43         lenc++;
 44     }
 45     c[lenc]=carry;
 46     while((!c[lenc])&&lenc>1) lenc--;
 47     put(lenc,c,1);
 48     return;
 49 }
 50 
 51 //高精度减法 
 52 template<typename type>
 53 inline void sub(char sa[],char sb[],type a[],type b[],type c[])
 54 {
 55     memset(a,0,sizeof(a));
 56     memset(b,0,sizeof(b));
 57     memset(c,0,sizeof(c));
 58     cin>>sa>>sb;
 59     int lena=strlen(sa),lenb=strlen(sb),lenc(0);
 60     char temp[MAXN];
 61     //"||"的优先级低于"&&"  //strcmp()为字符串比较函数，sa==sb返回0，s1>s2返回一个正整数，s1<s2返回一个负整数 
 62     if(lena<lenb || (lena==lenb)&&strcmp(sa,sb)<0)//处理被减数小于减数的情况 
 63     {
 64         strcpy(temp,sa);//将字符串sa复制到temp
 65         strcpy(sa,sb);
 66         strcpy(sb,temp);
 67         putchar('-');
 68         lena=strlen(sa),lenb=strlen(sb);
 69     }
 70     for(int i(1);i<=lena;i++) a[i]=sa[lena-i]^48;
 71     for(int i(1);i<=lenb;i++) b[i]=sb[lenb-i]^48;
 72     while(lenc<=lena||lenc<=lenb)
 73     {
 74         if(a[lenc]<b[lenc])
 75         {
 76             a[lenc]+=10;
 77             a[lenc+1]--;
 78         }
 79         c[lenc]=a[lenc]-b[lenc];
 80         lenc++;
 81     }
 82     while((!c[lenc])&&lenc>1) lenc--;
 83     put(lenc,c,1);
 84     return;
 85 }
 86 
 87 //高精度乘法 
 88 template<typename type>
 89 inline void mul(char sa[],char sb[],type a[],type b[],type c[])
 90 {
 91     memset(c,0,sizeof(c));
 92     get(sa,a,1);
 93     get(sb,b,1);
 94     int lena=strlen(sa),lenb=strlen(sb),lenc(0),carry(0);
 95     for(int i(1);i<=lena;i++)
 96     {
 97         carry=0;
 98         for(int j(1);j<=lenb;j++)
 99         {
100             c[i+j-1]=c[i+j-1]+a[i]*b[j]+carry;
101             carry=c[i+j-1]/10;
102             c[i+j-1]%=10;
103         }
104         c[i+lenb]=carry;
105     }
106     lenc=lena+lenb;
107     while((!c[lenc])&&lenc>1) lenc--;
108     put(lenc,c,1);
109     return;
110 }
111 
112 //高精度除法-高精除以低精(整除) 
113 template<typename type>
114 inline void div1(char sa[],type a[],type b,type c[])
115 {
116     memset(a,0,sizeof(a));
117     memset(c,0,sizeof(c));
118     cin>>sa>>b;
119     if(!b)
120     {
121         puts("0");
122         return;
123     }
124     int lena=strlen(sa),lenc(0);
125     ll carry(0);
126     for(int i(1);i<=lena;i++) a[i]=sa[i-1]^48;
127     for(int i(1);i<=lena;i++)//对被除数的每一位(包括余数)都除以除数 
128     {
129         c[i]=(carry*10+a[i])/b;
130         carry=(carry*10+a[i])%b;
131     }
132     lenc=1;
133     while((!c[lenc])&&lenc<lena) lenc++;
134     for(int i=lenc;i<=lena;i++) cout<<c[i];
135 }
136 
137 //高精度除法-高精除以高精(整除)
138 //用减法模拟除法，对被除数的每一位(包括余数)都减去除数，直到当前位置的数字(包括余数)小于除数 
139 template<typename type>
140 inline int comp(type a[],type b[])//比较a和b的大小关系，若a>b则为1，若a<b则为-1，若a=b则为0(类似于strcmp) 
141 {
142     if(a[0]>b[0]) return 1;
143     if(a[0]<b[0]) return -1;
144     for(int i=a[0];i>0;i--) //从最高位开始比较
145     {
146         if(a[i]>b[i]) return 1;
147         if(a[i]<b[i]) return -1;
148     }
149     return 0;
150 }
151 template<typename type>
152 inline void sub2(type a[],type b[])//计算a=a-b
153 {
154     int flag=comp(a,b);
155     if(!flag)
156     {
157         a[0]=0;
158         return;
159     }
160     if(flag=1)
161     {
162         for(int i=1;i<=a[0];i++)
163         {
164             if(a[i]<b[i])
165             {
166                 a[i]+=10;
167                 a[i+1]--;
168             }
169             a[i]-=b[i];
170         }
171         while((!a[a[0]])&&a[0]>0) a[0]--;
172         return;
173     }
174 }
175 template<typename type>
176 inline void div2(char sa[],char sb[],type a[],type b[],type c[])//在这里，x[0]存储的是x的位数 
177 {
178     memset(c,0,sizeof(c));
179     get(sa,a,1);//因为是逆序存，a[1]就是个位,a[lena]就是最高位 
180     get(sb,b,1);
181     int lena=strlen(sa),lenb=strlen(sb),lenc(0),carry(0),temp[MAXN];
182     if(lenb==1&&(!b))
183     {
184         puts("0");
185         return;
186     }
187     a[0]=lena,b[0]=lenb,c[0]=a[0]-b[0]+1;//商的位数不超过被除数的位数－除数的位数+1
188     for(int i=c[0];i>0;i--)
189     {
190         memset(temp,0,sizeof(temp));
191         for(int j=1;j<=b[0];j++) temp[j+i-1]=b[j];//复制b数组到temp数组从i开始的地方 
192         temp[0]=b[0]+i-1;
193         while(comp(a,temp)>=0)
194         {
195             c[i]++;
196             sub2(a,temp);
197         }
198     }
199     
200     while((!c[c[0]])&&c[0]>0) c[0]--;//处理前导0 
201     
202     if(!c[0]) puts("0");//输出商 
203     else
204     {
205         for(int i=c[0];i>0;i--) cout<<c[i];
206         puts("");
207     }
208     
209     if(!a[0]) puts("0");//输出余数 
210     else
211     {
212         for(int i=a[0];i>0;i--) cout<<a[i];
213         puts("");
214     }
215     return;
216 }
217 
218 signed main()
219 {
220     add(sa,sb,a,b,c);
221     sub(sa,sb,a,b,c);
222     mul(sa,sb,a,b,c);
223     div1(sa,a,d,c);
224     div2(sa,sb,a,b,c);
225     return 0;
226 }