华师一附中OI组

标题: 20210811网课第一题 高精度除法 [打印本页]

---

作者: admin    时间: 2021-8-11 09:09
标题: 20210811网课第一题 高精度除法
输入两个正整数，都不超过1000位，求他们的商和余数。
比如输入100  3  输出33  1
比如输入1000 10  输出100  0

---

作者: admin    时间: 2021-8-11 09:09

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. string a,b,c,r,b09[10],ta;
   
4. bool isbig(string x,string y) // 判断大小
   
5. {
   
6.         bool b1=x.size()>y.size();
   
7.         bool b2=(x.size()==y.size()) && (x>y);
   
8.         return b1||b2;
   
9. }
   
10. 
    
11. string add(string x,string y)
    
12. {
    
13.         if (isbig(y,x)) swap(x,y);
    
14.         int lx=x.size(),ly=y.size();
    
15.         for (int p=1; p<=lx-ly; p++) y="0"+y; // 短的前面添0
    
16.         int j=0;
    
17.         string z=""; // 一定要有初值
    
18.         for(int p=lx-1; p>=0; p--) //  从右往左加
    
19.                 {
    
20.                         int x1=x[p]-'0',x2=y[p]-'0';
    
21.                         int x3=x1+x2+j;
    
22.                         if (x3>9)
    
23.                                 {
    
24.                                         x3-=10;
    
25.                                         j=1;
    
26.                                 }
    
27.                         else j=0;
    
28.                         z=char('0'+x3)+z; //右左
    
29.                 }
    
30.         if(j==1) z="1"+z;
    
31.         return z;
    
32. }
    
33. string sub(string x,string y)
    
34. {
    
35.         int lx=x.size(),ly=y.size();
    
36.         for (int p=1; p<=lx-ly; p++) y='0'+y; // 短的前面添0
    
37.         int j=0;
    
38.         string z=""; // 一定要有初值
    
39.         for(int p=lx-1; p>=0; p--) //  从右往左加
    
40.                 {
    
41.                         int x3=x[p]-y[p]-j;
    
42.                         if (x3<0)
    
43.                                 {
    
44.                                         x3+=10;
    
45.                                         j=1;
    
46.                                 }
    
47.                         else j=0;
    
48. 
    
49.                         z=char('0'+x3)+z; //右左
    
50.                 }
    
51.         while (z[0]=='0' && z.size()>1) z.erase(0,1); // 去掉最高位的0  
    
52.         return z;
    
53. }
    
54. void getb09()
    
55. {
    
56.         b09[0]='0',b09[1]=b;
    
57.         for (int i=2; i<=9; i++) b09[i]=add(b09[i-1],b);
    
58. }
    
59. int main()
    
60. {
    
61.         cin>>a>>b;
    
62.         int la=a.size(),lb=b.size();
    
63.         ta=r=c="";
    
64.         getb09();
    
65.         //CKECK for (int i=0;i<=9;i++) cout<<b09[i]<<endl;
    
66.         r=a.substr(0,lb-1); // 找到同样长度的 再来
    
67.         for (int p=lb-1; p<=la-1; p++) //  从左往右除
    
68.                 {
    
69.                         ta=r+a[p]; //添1位成为新的被除数
    
70.                         int k=9;
    
71.                         while (isbig(b09[k],ta))  k--; // 试商
    
72.                         c=c+char('0'+k); // 左右
    
73.                         r=sub(ta,b09[k]);
    
74.                 }
    
75.                 while (c[0]=='0' && c.size()>1) c.erase(0,1); // 去掉最高位的0  
    
76.                 while (r[0]=='0' && r.size()>1) r.erase(0,1); // 去掉最高位的0  
    
77.         cout<<c;
    
78.         //<<' '<<r;
    
79.         return 0;
    
80. }
    
81. /*
    
82. 10  3
    
83. 12345  5
    
84. 123456789987654321 123456789
    
85. 999999999999999999999999999999999999   99999999999999999999
    
86. */

复制代码

---

作者: 孔某某某    时间: 2021-8-11 09:42
#include <bits/stdc++.h>
using namespace std;
int a[100010],b[100010],c[100010],d,i;
void init(int a[])//初始化
{
        string s;
        cin>>s;
        a[0]=s.length();
        for (i=1; i<=a[0]; i++)
                a[i]=s[a[0]-i]-'0';
}
void print(int a[])
{
        int i;
        if (a[0]==0)
        {
                cout<<0<<endl;
                return;
        }
        for (i=a[0]; i>0; i--)
                cout<<a[i];
        return ;
}//输出
int compare (int a[],int b[])
{
        int i;
        if (a[0]>b[0])
                return 1;
        if (a[0]<b[0])
                return -1;
        for (i=a[0]; i>0; i--)
        {
                if (a[i]>b[i])
                        return 1;
                if (a[i]<b[i])
                        return -1;
        }
        return 0;
}
void jian(int a[],int b[])//减法
{
        int flag,i;
        flag=compare(a,b);
        if (flag==0)
        {
                a[0]=0;
                return ;
        }
        if (flag==1)
        {
                for (i=1;i<=a[0];i++)
                {
                        if (a[i]<b[i])
                        {
                                a[i+1]--;
                                a[i]+=10;
                        }
                        a[i]-=b[i];
                }
                while (a[0]>0&&a[a[0]]==0)
                a[0]--;
                return ;
        }
}
void numcpy(int p[],int q[],int det)
{
        for (int i=1;i<=p[0];i++)
        q[i+det-1]=p[i];
        q[0]=p[0]+det-1;
} //对齐位数
void chugao(int a[],int b[],int c[])
{
        int i,tmp[100010];
        c[0]=a[0]-b[0]+1;
        for (i=c[0];i>0;i--)
        {
                memset(tmp,0,sizeof(tmp));
                numcpy(b,tmp,i);
                while (compare(a,tmp)>=0)
                {
                        c[i]++;
                        jian(a,tmp);
                }
        }
        while (c[0]>0&&c[c[0]]==0)
        c[0]--;
        return ;
}
int main()
{
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        init(a);
        init(b);
        chugao(a,b,c);
        print(c);
        cout<<" ";
        print(a);
        return 0;
}

---

作者: admin    时间: 2021-8-11 11:28
孔同学，很好！但是我真的墙裂不建议c[0]表示长度。其实你可以用一个结构体、

---

作者: 非液化    时间: 2021-8-11 16:10

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. string a,b,s,b09[10],outPut;//输入a,b
   
4. int la,lb;
   
5. int isBig(string x, string y)
   
6. {
   
7.         int lx=x.size();
   
8.         int ly=y.size();
   
9.         if(lx>ly||(lx==ly&&x>y))
   
10.         return 0;
    
11.         else return 1;
    
12. }
    
13. string highAdd(string x,string y)//高精度加法
    
14. {
    
15.         int lx=x.size();
    
16.         int ly=y.size();
    
17.         string t="";//临时存储
    
18.         if(isBig(x,y)==0)//小的前面添0
    
19.         {
    
20.                 for(int i=1;i<=lx-ly;i++)
    
21.                 y="0"+y;
    
22.         }
    
23.         else
    
24.         {
    
25.                 for(int i=1;i<=ly-lx;i++)
    
26.                 x="0"+x;
    
27.         }
    
28.         int j=0;//进位
    
29.         for(int i=max(lx,ly)-1;i>=0;i--)
    
30.         {
    
31.                 int n=x[i]-'0'+y[i]-'0'+j;
    
32.                 if(n>9)
    
33.                 {
    
34.                         j=1;
    
35.                         n-=10;
    
36.                 }
    
37.                 else j=0;
    
38.                 t=char(n+'0')+t;
    
39.         }
    
40.         if(j!=0)
    
41.         {
    
42.                 t=char(j+'0')+t;
    
43.         }
    
44.         return t;
    
45. }
    
46. void getb09()//
    
47. {
    
48.         b09[0]='0';
    
49.         b09[1]=b;
    
50.         for(int i=2;i<=9;i++)
    
51.         {
    
52.                 b09[i]="";
    
53.                 b09[i]=highAdd(b09[i-1],b);
    
54.         }
    
55. }
    
56. string highSub(string x,string y)
    
57. {
    
58.         int lx=x.size();
    
59.         int ly=y.size();
    
60.         string t="";//临时存储
    
61.         for(int i=1;i<=lx-ly;i++)
    
62.         y="0"+y;
    
63.         int j=0;//退位
    
64.         for(int i=lx-1;i>=0;i--)
    
65.         {
    
66.                 int n=x[i]-y[i]+j;
    
67.                 if(n<0)
    
68.                 {
    
69.                         j=-1;
    
70.                         n+=10;
    
71.                 }
    
72.                 else j=0;
    
73.                 t=char(n+'0')+t;
    
74.         }
    
75.         while(t[0]=='0'&&t.size()>0)
    
76.         {
    
77.                 t.erase(0,1);
    
78.         }
    
79.         return t;
    
80. }
    
81. void highDiv()
    
82. {
    
83.         s=a.substr(0,lb);
    
84.         outPut="";
    
85.         for(int i=lb-1;i<la;i++)
    
86.         {
    
87.                 int j=9;
    
88.                 while((isBig(b09[j],s)==0)&&j!=0)//试商
    
89.                 {
    
90.                         j--;
    
91.                 }
    
92.                 outPut=outPut+char(j+'0');
    
93.                 s=highSub(s,b09[j])+a[i+1];
    
94.         }
    
95. }
    
96. int main()
    
97. {
    
98.         cin>>a>>b;
    
99.         la=a.size();
    
100.         lb=b.size();
     
101.         getb09();
     
102.     highDiv();
     
103.     while(outPut[0]=='0'&&outPut.size()!=0)
     
104.     {
     
105.             outPut.erase(0,1);//最高位去0
     
106.         }
     
107.         cout<<outPut<<endl<<s;
     
108.         return 0;
     
109.        
     
110. }
     

复制代码

---

作者: 651979223    时间: 2021-8-11 16:36

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. string a,b,c,d,g[10],a1;//a被除数，b除数，c商，d余数 ,a1过程被除数
   
4. bool daxiao(string x,string y)
   
5. {
   
6.         bool b1,b2;
   
7.         int lx=x.size(),ly=y.size();
   
8.         b1=lx>ly;
   
9.         b2=(lx==ly)&&(x>y);
   
10.         return b1||b2;
    
11. }
    
12. string jia(string x,string y)
    
13. {
    
14.         string z="";int flag=0;//进位标识
    
15.         if(daxiao(y,x)) swap(x,y);
    
16.         int lx=x.size(),ly=y.size();
    
17.         for(int p=0;p<lx-ly;p++)
    
18.         y='0'+y;//补0
    
19.         for(int j=lx-1;j>=0;j--)
    
20.           {
    
21.           int x1=x[j]-'0',y1=y[j]-'0',z1=x1+y1+flag;
    
22.           if(z1>9)
    
23.           {
    
24.                   z1%=10;
    
25.                   flag=1;
    
26.           }
    
27.           else flag=0;
    
28.           z=char('0'+z1)+z;
    
29.           }
    
30.           if(flag==1) z='1'+z;
    
31.           return z;
    
32. }
    
33. string jian(string x,string y)
    
34. {
    
35.         string z="";int flag=0;//退位标识
    
36.         int lx=x.size(),ly=y.size();
    
37.         for(int p=0;p<lx-ly;p++)
    
38.         y='0'+y;//补0
    
39.         for(int j=lx-1;j>=0;j--)
    
40.           {
    
41.           int x1=x[j]-'0',y1=y[j]-'0',z1=x1-y1-flag;
    
42.           if(z1<0)
    
43.           {
    
44.                   z1+=10;
    
45.                   flag=1;
    
46.           }
    
47.           else flag=0;
    
48.           z=char('0'+z1)+z;
    
49.           }
    
50.           while (z[0]=='0' && z.size()>1) z.erase(0,1);
    
51.           return z;
    
52. }
    
53. void chuprocess()//试商函数
    
54. {
    
55.         g[0]='0';g[1]=b;
    
56.         for(int i=2;i<=9;i++) g[i]=jia(g[i-1],b);
    
57.   }
    
58.   int main()
    
59.   {
    
60.           cin>>a>>b;
    
61.     int la=a.size(),lb=b.size();
    
62.     a1=c=d="";
    
63.         chuprocess();
    
64.         d=a.substr(0,lb-1);
    
65.          for (int p=lb-1; p<=la-1; p++)
    
66.          {
    
67.                  a1=d+a[p];
    
68.                  int s=9;
    
69.                  while(daxiao(g[s],a1)==1) s--;
    
70.                  c=c+char(s+'0');
    
71.                  d=jian(a1,g[s]);
    
72.          }
    
73.          while(c[0]=='0' && c.size()>1) c.erase(0,1);
    
74.          while(d[0]=='0'&&d.size()>1) d.erase(0,1);
    
75.          cout<<c<<" "<<d;
    
76.          return 0;
    
77.   }

复制代码

---

作者: demonlover    时间: 2021-8-11 18:28
#include <bits/stdc++.h>
using namespace std;
string sa,sb,c="",r,b19[10],ta="";//sa被除数sb除数sc结果r余数ta新被除数

void getb19();//计算除数的1-9倍
bool isbig(string ,string);//字符串代表的数字比大小
string add(string ,string);//高精度加
string sub(string ,string);//高精度减

void getb19()
{
        b19[0]="0",b19[1]=sb;
        for(int i=2;i<=9;i++)
                        b19[i]=add(b19[i-1],sb);
}

bool isbig(string x,string y)
{
        if(x.size()==y.size()) return x>y;
        return x.size()>y.size();
}

string add(string x,string y)//高精度加
{
    int qq[100000],ww[100000],ee[100000];
        int lenx,leny,lenz;
        string z="";
        memset(qq,0,sizeof(qq));
        memset(ww,0,sizeof(ww));
        memset(ee,0,sizeof(ee));
        lenx=x.size();
        leny=y.size();
        for(int i=0;i<=lenx-1;i++)
                qq[i]=x[lenx-1-i]-'0';
        for(int i=0;i<=leny-1;i++)
                ww[i]=sb[leny-1-i]-'0';
        lenz=0;
        int tx=0;
        while(lenz<=lenx-1||lenz<=leny-1)
        {
                ee[lenz]=qq[lenz]+ww[lenz]+tx;
                tx=ee[lenz]/10;
                ee[lenz]%=10;
                lenz++;
        }
        ee[lenz]=tx;
        if(ee[lenz]==0)
                lenz--;
        for(int i=0;i<=lenz;i++)
            z=z+char(ee[lenz-i]+'0');
    return z;
}

string sub(string x,string y)//高精度减
{
        int qq[100000],ww[100000],ee[100000];
        int lenx,leny,lenz;
        string z="",s;//schange
        memset(qq,0,sizeof(qq));
        memset(ww,0,sizeof(ww));
        memset(ee,0,sizeof(ee));
        lenx=x.size();
        leny=y.size();
        for(int i=0;i<=lenx-1;i++)
                qq[i]=x[lenx-1-i]-'0';
        for(int i=0;i<=leny-1;i++)
                ww[i]=y[leny-1-i]-'0';
        lenz=0;
        while(lenz<=lenx-1||lenz<=leny-1)
        {
                if(qq[lenz]<ww[lenz])
                {
                        qq[lenz]+=10;
                        qq[lenz+1]--;
                }
                ee[lenz]=qq[lenz]-ww[lenz];
                lenz++;
        }
        while((ee[lenz]==0)&&lenz>0)
                lenz--;
        for(int i=0;i<=lenz;i++)
            z=z+char(ee[lenz-i]+'0');
    return z;
}

int main()
{
                int lena,lenb;
        cin>>sa>>sb;
               lena=sa.size();
                lenb=sb.size();
        getb19();
        r=sa.substr(0,lenb-1);
        for(int p=lenb-1;p<=lena-1;p++)
        {
                if(r=="0") ta=sa[p];
                else ta=r+sa[p];
            int k=9;
            while(isbig(b19[k],ta)) k--;//如果比新被除数大就小一倍
            c=c+char(k+'0');
            r=sub(ta,b19[k]);
        }
        while(c[0]=='0'&&c.size()>1) c.erase(0,1);
        while(r[0]=='0'&&r.size()>1) r.erase(0,1);
        cout<<c;
        return 0;
}

---

作者: demonlover    时间: 2021-8-11 18:30
老师，69排有问题，如果余数不是零的话就加，否则就不加了。如果把零加上去，新的被除数长度就多了一位，用isbig判断的时候就出问题了。

---

作者: Crystal1129    时间: 2021-8-11 20:49

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. string a,b,c,r,b09[10],ta;
   
4. bool isbig(string x,string y)
   
5. {
   
6.         bool b1=x.size()>y.size();
   
7.         bool b2=(x.size()==y.size()) && (x>y);
   
8.         return b1||b2;
   
9. }
   
10. string add(string x,string y)
    
11. {
    
12.         if(isbig(y,x)) swap(x,y);
    
13.         int lx=x.size(),ly=y.size();
    
14.         for(int p=1;p<=lx-ly;p++) y='0'+y;
    
15.         int j=0;
    
16.         string z="";
    
17.         for(int p=lx-1;p>=0;p--)
    
18.         {
    
19.                 int x1=x[p]-'0',x2=y[p]-'0';
    
20.                 int x3=x1+x2+j;
    
21.                 if(x3>9) {x3-=10;j=1;}
    
22.                 else j=0;
    
23.                 z=char('0'+x3)+z;
    
24.         }
    
25.         if(j==1) z='1'+z;
    
26.         return z;
    
27. }
    
28. string sub(string x,string y)
    
29. {
    
30.         int lx=x.size(),ly=y.size();
    
31.         for(int p=1;p<=lx-ly;p++) y='0'+y;
    
32.         int j=0;
    
33.         string z="";
    
34.         for(int p=lx-1;p>=0;p--)
    
35.         {
    
36.                 int x3=x[p]-y[p]-j;
    
37.                 if(x3<0)
    
38.                 {
    
39.                         x3+=10;
    
40.                         j=1;
    
41.                 }
    
42.                 else j=0;
    
43.                 z=char('0'+x3)+z;
    
44.         }
    
45.         while(z[0]=='0' && z.size()>1) z.erase(0,1);
    
46.         return z;
    
47. }
    
48. void getb09()
    
49. {
    
50.         b09[0]='0',b09[1]=b;
    
51.         for(int i=2;i<=9;i++) b09[i]=add(b09[i-1],b);
    
52. }
    
53. int main()
    
54. {
    
55.         cin>>a>>b;
    
56.         int la=a.size();
    
57.         int lb=b.size();
    
58.         ta=r=c="";
    
59.         getb09();
    
60.         r=a.substr(0,lb-1);
    
61.         for(int p=0;p<la;p++)
    
62.         {
    
63.                 ta=r+a[p];
    
64.                 int k=9;
    
65.                 while(isbig(b09[k],ta)) k--;
    
66.                 c=c+char('0'+k);
    
67.                 r=sub(ta,b09[k]);
    
68.         }
    
69.         while(c[0]=='0' && c.size()>1) c.erase(0,1);
    
70.         while(r[0]=='0' && r.size()>1) r.erase(0,1);
    
71.         cout<<c<<' '<<r;
    
72.         return 0;
    
73. }

复制代码

---

作者: 神域鬼手    时间: 2021-8-12 08:05

1. //数组做法（会超时）
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. string a,b,c="";
   
5. string x,r;
   
6. string b09[10];
   
7. string add(string x,string y)
   
8. {
   
9.         int mm=22000;
   
10.         int sa[mm],sb[mm],sc[mm];
    
11.         for(int i=0;i<=mm-1;i++)
    
12.         {
    
13.                 sa[i]=0;
    
14.                 sb[i]=0;
    
15.                 sc[i]=0;
    
16.         }
    
17.         string z="";
    
18.         int lx=x.size();
    
19.         int ly=y.size();
    
20.         for(int i=0;i<=lx-1;i++)
    
21.         sa[i]=x[lx-i-1]-'0';
    
22.         for(int i=0;i<=ly-1;i++)
    
23.         sb[i]=y[ly-i-1]-'0';
    
24.         for(int i=0;i<=mm-1;i++)
    
25.         sc[i]=sa[i]+sb[i];
    
26.         for(int i=0;i<=mm-1;i++)
    
27.         {
    
28.                 sc[i+1]+=sc[i]/10;
    
29.                 sc[i]=sc[i]%10;
    
30.         }
    
31.         int i=mm-1;
    
32.         while(sc[i]==0&&i>0)
    
33.         i--;
    
34.         for(int j=0;j<=i;j++)
    
35.         z=char(sc[j]+48)+z;
    
36.         return z;
    
37. }
    
38. string sub(string x,string y)
    
39. {
    
40.         int mm=22000;
    
41.         int sa[mm],sb[mm],sc[mm];
    
42.         for(int i=0;i<=mm-1;i++)
    
43.         {
    
44.                 sa[i]=0;
    
45.                 sb[i]=0;
    
46.                 sc[i]=0;
    
47.         }
    
48.         string z="";
    
49.         int lx=x.size();
    
50.         int ly=y.size();
    
51.         for(int i=0;i<=lx-1;i++)
    
52.         sa[i]=x[lx-i-1]-'0';
    
53.         for(int i=0;i<=ly-1;i++)
    
54.         sb[i]=y[ly-i-1]-'0';
    
55.         for(int i=0;i<=mm-1;i++)
    
56.         sc[i]=sa[i]-sb[i];
    
57.         for(int i=0;i<=mm-1;i++)
    
58.         {
    
59.                 if(sc[i]<0)
    
60.                 {
    
61.                         sc[i]+=10;
    
62.                         sc[i+1]--;
    
63.                 }
    
64.         }
    
65.         int i=mm-1;
    
66.         while(sc[i]==0&&i>0)
    
67.         i--;
    
68.         for(int j=0;j<=i;j++)
    
69.         z=char(sc[j]+48)+z;
    
70.         return z;
    
71. }
    
72. bool isbig(string x,string y)
    
73. {
    
74.         bool b;
    
75.         b=false;
    
76.         int lx=x.size();
    
77.         int ly=y.size();
    
78.         if((lx>ly)||(lx==ly&&x>y))
    
79.         b=true;
    
80.         return b;
    
81. }
    
82. void getb09()
    
83. {
    
84.         b09[0]='0';
    
85.         for(int i=1;i<=9;i++)
    
86.         b09[i]=add(b09[i-1],b);
    
87. }
    
88. int main()
    
89. {
    
90.         cin>>a>>b;
    
91.         getb09();
    
92.         int la=a.size();
    
93.         for(int p=0;p<=la-1;p++)
    
94.         {
    
95.                 x=r+a[p];
    
96.                 int k=9;
    
97.                 while(isbig(b09[k],x))
    
98.                 k--;
    
99.                 c=c+char(k+'0');
    
100.                 r=sub(x,b09[k]);
     
101.         }
     
102.         int lc=c.size();
     
103.         int i=0;
     
104.         while(c[i]=='0'&&i<lc-1)
     
105.         i++;
     
106.         for(;i<=lc-1;i++)
     
107.         cout<<c[i];
     
108.         return 0;
     
109. }
     
110. 
     
111. 
     
112. 
     
113. 
     
114. 
     
115. //字符串做法（ac）
     
116. #include<bits/stdc++.h>
     
117. using namespace std;
     
118. string a,b,c="";
     
119. string x,r;
     
120. string b09[10];
     
121. string add(string x,string y)
     
122. {
     
123.         string z="";
     
124.         int j=0;
     
125.         int lx=x.size();
     
126.         int ly=y.size();
     
127.         int maxl=max(lx,ly);
     
128.         for(int i=lx;i<=maxl;i++)
     
129.         x='0'+x;
     
130.         for(int i=ly;i<=maxl;i++)
     
131.         y='0'+y;
     
132.         for(int i=maxl;i>=0;i--)
     
133.         {
     
134.                 int x1=x[i]-'0';
     
135.                 int x2=y[i]-'0';
     
136.                 int x3=x1+x2+j;
     
137.                 if(x3>9)
     
138.                 {
     
139.                         x3-=10;
     
140.                         j=1;
     
141.                 }
     
142.                 else j=0;
     
143.                 z=char(x3+'0')+z;
     
144.         }
     
145.         while(z[0]=='0')
     
146.                 z.erase(0,1);
     
147.         return z;
     
148. }
     
149. string sub(string x,string y)
     
150. {
     
151.         string z="";
     
152.         int j=0;
     
153.         int lx=x.size();
     
154.         int ly=y.size();
     
155.         int maxl=max(lx,ly);
     
156.         for(int i=lx;i<=maxl;i++)
     
157.         x='0'+x;
     
158.         for(int i=ly;i<=maxl;i++)
     
159.         y='0'+y;
     
160.         for(int i=maxl;i>=0;i--)
     
161.         {
     
162.                 int x1=x[i]-'0';
     
163.                 int x2=y[i]-'0';
     
164.                 int x3=x1-x2-j;
     
165.                 if(x3<0)
     
166.                 {
     
167.                         x3+=10;
     
168.                         j=1;
     
169.                 }
     
170.                 else j=0;
     
171.                 z=char(x3+'0')+z;
     
172.         }
     
173.         while(z[0]=='0')
     
174.                 z.erase(0,1);
     
175.         return z;
     
176. }
     
177. bool isbig(string x,string y)
     
178. {
     
179.         bool b;
     
180.         b=false;
     
181.         int lx=x.size();
     
182.         int ly=y.size();
     
183.         if((lx>ly)||(lx==ly&&x>y))
     
184.         b=true;
     
185.         return b;
     
186. }
     
187. void getb09()
     
188. {
     
189.         b09[0]='0';
     
190.         for(int i=1;i<=9;i++)
     
191.         b09[i]=add(b09[i-1],b);
     
192. }
     
193. int main()
     
194. {
     
195.         cin>>a>>b;
     
196.         getb09();
     
197.         int la=a.size();
     
198.         r=a.substr(0,b.size()-1);
     
199.         for(int p=b.size()-1;p<=la-1;p++)
     
200.         {
     
201.                 x=r+a[p];
     
202.                 int k=9;
     
203.                 while(isbig(b09[k],x))
     
204.                 k--;
     
205.                 c=c+char(k+'0');
     
206.                 r=sub(x,b09[k]);
     
207.         }
     
208.         int lc=c.size();
     
209.         int i=0;
     
210.         while(c[i]=='0'&&i<lc-1)
     
211.         i++;
     
212.         for(;i<=lc-1;i++)
     
213.         cout<<c[i];
     
214.         return 0;
     
215. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2