P2005 A/B Problem II

admin

https://www.luogu.com.cn/problem/P2005

题目背景
为了让大家紧张的心情放松一下，这一题题是一道非常简单的题目。

题目描述
给出正整数N和M，请你计算N div M（N/M的下取整）。

输入格式
两行，两个正整数，N和M。

输出格式
一行，一个整数，表示N div M。

输入输出样例
输入 #1复制
1000
333
输出 #1复制
3
说明/提示
• 对于60%的数据：N，M ≤ 750!，答案≤ 7!。

• 对于100%的数据：N，M ≤ 6250!，答案≤ 13!。

请注意：上面的两句话并不是感叹句，而是陈述句。标点符号使用没有错误。

admin

估计下N和M有多少位，敲了个高精度阶乘，算了半分钟，得出750!有21012位。这么大的数字，存起来还需要考虑数组的长度，假设22000位吧。
第一种方法，硬除。22000位的大数除普通longlong整数，也就只有22000次求商和取余，不会超时。
第二种方法，二分法。这个就比较新颖了，我们假设商的范围是L-R之间，去之间值M，和除数M做单精度乘法，得到乘积X，看看X和N的大小，

admin

1. #include  <bits/stdc++.h>
   
2. using namespace std;
   
3. string A,B,C; //A/B=C
   
4. string B09[10]; // 除数的0-9倍
   
5. bool isbig(string X,string Y) //字符串当数字比较大小
   
6. {
   
7.         int lx=X.size(),ly=Y.size();
   
8.         return (lx>ly)||(lx==ly && X>=Y);
   
9. }
   
10. string add(string A,string B) //基本高精加
    
11. {
    
12.         string C="";
    
13.         if (A.size()<B.size()) swap(A,B);
    
14.         int la=A.size(),lb=B.size(),i;
    
15.         for (i=lb+1; i<=la; i++) B="0"+B;
    
16.         int j=0;
    
17.         for (i=la-1; i>=0; i--)
    
18.                 {
    
19.                         int x=A[i]-'0'+B[i]-'0'+j;
    
20.                         j=x/10;
    
21.                         x=x%10;
    
22.                         C=char(x+'0')+C;
    
23.                 }
    
24.         if (j) C="1"+C;
    
25.         return C;
    
26. }
    
27. string sub(string A,string B)  //基本高精减
    
28. {
    
29.         string C="";
    
30.         int la=A.size(),lb=B.size(),i,j=0,x;
    
31.         for (i=lb+1; i<=la; i++) B="0"+B;
    
32.         for (i=la-1; i>=0; i--)
    
33.                 {
    
34.                         x=A[i]-B[i]-j;
    
35.                         if (x<0)
    
36.                                 {
    
37.                                         j=1;
    
38.                                         x+=10;
    
39.                                 }
    
40.                         else j=0;
    
41.                         C=char(x+'0')+C;
    
42.                 }
    
43.         int p=0;
    
44.         while (C[p]=='0' && p<la-1) p++;
    
45.         return C.substr(p);
    
46. }
    
47. void CB09(string B)
    
48. {
    
49.         B09[0]="0",B09[1]=B;
    
50.         for (int i=2; i<=9; i++)B09[i]=add(B09[i-1],B);
    
51.         ///for (int i=0; i<=9; i++) cout<<B09[i]<<endl;
    
52. }
    
53. int main()
    
54. {
    
55.         cin>>A>>B;
    
56.         CB09(B);
    
57.         int la=A.size(),lb=B.size(),p;
    
58.         string TA=A.substr(0,lb);
    
59.         if (isbig(TA,B)) p=lb;
    
60.         else
    
61.                 {
    
62.                         TA=TA+A[lb];
    
63.                         p=lb+1;
    
64.                 }
    
65.         for(; p<=la; p++)
    
66.                 {
    
67.                         int k=9;
    
68.                         while (!isbig(TA,B09[k]))k--;
    
69.                         C=C+char(k+'0');
    
70.                         //cout<<TA<<' '<<C<<endl;
    
71.                         TA=sub(TA,B09[k]);
    
72.                         //cout<<TA<<endl;
    
73.                         TA=TA+A[p];
    
74.                         while (TA[0]=='0' && TA.size()>1) TA.erase(0,1);//去前面的0
    
75.                 }
    
76.         cout<<C;
    
77.         return 0;
    
78. }

复制代码

admin

也可以用二分法来做这个题，显然，这个题满足二分法的条件，若X*B>A，则所有>=X的都不满足条件，若X*B<=A,则有可能在这个区间内找到答案。
先写一个不高精度的，典型的二分找下界。等下我们用点新玩意，高精度的运算符的重载。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. typedef long long LL;
   
4. LL A,B,C,L,R,M,ANS;
   
5. int main()
   
6. {
   
7.         cin>>A>>B;
   
8.         L=0;
   
9.         R=6227020800l;
   
10.         while (L<=R)
    
11.                 {
    
12.                         M=(L+R)/2;
    
13.                         X=M*B;
    
14.                         if (X<=A)
    
15.                                 {
    
16.                                         ANS=M;
    
17.                                         L=M+1;
    
18.                                 }
    
19.                         else if (X>A) R=M-1;
    
20.                 }
    
21.         cout<<ANS;
    
22.         return 0;
    
23. }

复制代码

admin

加入高精度过程，这里为了统一，我采用运算符重定义的做法，用结构题BigNum表示一个数，带两个变量，一个有效长度l和一个数组a。
重新定义了几个运算符：
1、<= 这个比较简单，短的比较小长的比较大，长度相等的话就从从第一个开始比较，不同的数字就比出来了结果。
2、* 大整数相乘 这个也很简单，标准的矩阵乘法，最后处理进位和长度，一般来说n位数*m位数得到n+m或者n+m-1位。（0没有考虑）
3、+ 分两个，大+小或者大+大。这都是以前的范例程序
4、- 这里只有一个M+1和M-1。但是也标准的写一个，注意%的使用，我这里比较巧妙。有可能减很大的数字，注意。
5、/ 大除小，基本的355/113的做法 但是多了一个去前面的0的过程，这里也可以类似上面的先比较再除，

我写了十几分钟，基本没有调试，一下就AC了，因为我这些基本功很到位的，你做了多少时间呢？
附·AC代码

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. struct BigNum
   
4. {
   
5.         int l;//位数
   
6.         int a[22000];
   
7.         BigNum()//初始化
   
8.         {
   
9.                 memset(a,sizeof(a),0);
   
10.                 l=1;
    
11.         }
    
12.         void pp() //输出
    
13.         {
    
14.                 for (int i=l-1; i>=0; i--) cout<<a[i];
    
15.                 cout<<' ';
    
16.         }
    
17. } A,B,C,L,R,M,X,ANS;
    
18. bool operator <= (BigNum A,BigNum B)// 大的比大的
    
19. {
    
20.         if(A.l>B.l) return 0;
    
21.         if(A.l<B.l) return 1;
    
22.         for (int i=A.l-1; i>=0; i--) // 这个比较精妙
    
23.                 if (A.a[i]<B.a[i]) return 1;
    
24.                 else if (A.a[i]>B.a[i]) return 0;
    
25.         return 1;
    
26. }
    
27. BigNum operator * (BigNum A,BigNum B)// 大的乘大的
    
28. {
    
29.         BigNum  C;
    
30.         int i,j,x;
    
31.         C.l=A.l+B.l;
    
32.         for (i=0; i<=C.l-1; i++) C.a[i]=0;
    
33.         for (i=0; i<=A.l-1; i++)
    
34.                 for (j=0; j<=B.l-1; j++)
    
35.                         C.a[i+j]+=A.a[i]*B.a[j];
    
36.         for (i=0; i<=C.l-1; i++)
    
37.                 {
    
38.                         x=C.a[i];
    
39.                         C.a[i]=x%10;
    
40.                         C.a[i+1]+=x/10;
    
41.                 }
    
42.         while (C.a[C.l-1]==0 && C.l>1) C.l--;
    
43.         return C;
    
44. }
    
45. BigNum operator + (BigNum A,BigNum B)// 大的加大的
    
46. {
    
47.         if (A.l<B.l) swap(A,B);
    
48.         int x,i;
    
49.         for (i=0; i<=B.l-1; i++) A.a[i]+=B.a[i];
    
50.         for (i=0; i<=A.l-1; i++)
    
51.                 {
    
52.                         x=A.a[i];
    
53.                         A.a[i]=x%10;
    
54.                         A.a[i+1]+=x/10;
    
55.                 }
    
56.         if (A.a[A.l]>0)A.l++;
    
57.         return A;
    
58. }
    
59. BigNum operator + (BigNum A,int b)
    
60. {
    
61.         int x,i;
    
62.         A.a[0]+=b;
    
63.         for (i=0; i<=A.l-1; i++)
    
64.                 {
    
65.                         x=A.a[i];
    
66.                         A.a[i]=x%10;
    
67.                         A.a[i+1]+=x/10;
    
68.                 }
    
69.         if (A.a[A.l]>0) A.l++;
    
70.         return A;
    
71. }
    
72. BigNum operator - (BigNum A,int b)
    
73. {
    
74.         int x,i;
    
75.         A.a[0]-=b;
    
76.         for (i=0; i<=A.l-1; i++)
    
77.                 {
    
78.                         x=A.a[i];
    
79.                         if (x<0) //这个我觉得写的很好
    
80.                                 {
    
81.                                         A.a[i]=x%10+10;
    
82.                                         A.a[i+1]+=(x/10-1);
    
83.                                 }
    
84.                 }
    
85.         while (A.a[A.l-1]==0 && A.l>0) A.l--;
    
86.         return A;
    
87. }
    
88. BigNum operator / (BigNum A,int b)
    
89. {
    
90.         int i,x=0;
    
91.         for (i=A.l-1; i>=0; i--)
    
92.                 {
    
93.                         x=10*x+A.a[i];
    
94.                         A.a[i]=x/b;
    
95.                         x=x%b;
    
96.                 }
    
97.         while (A.a[A.l-1]==0 && A.l>0) A.l--;
    
98.         return A;
    
99. }
    
100. BigNum Ch(string s)
     
101. {
     
102.         int l=s.size();
     
103.         BigNum A;
     
104.         A.l=l;
     
105.         for (int i=0; i<=l; i++) A.a[i]=s[l-1-i]-'0';
     
106.         return A;
     
107. }
     
108. int main()
     
109. {
     
110.         string sa,sb;
     
111.         cin>>sa>>sb;
     
112.         A=Ch(sa),B=Ch(sb);
     
113.         L=Ch("0"),R=Ch("99999999999");
     
114.         while (L<=R)
     
115.                 {
     
116. 
     
117.                         M=(R+L)/2;
     
118.                         X=M*B;
     
119.                         //L.pp(),R.pp(),M.pp(),X.pp();
     
120.                         //cout<<endl;
     
121.                         if (X<=A)
     
122.                                 {
     
123.                                         ANS=M;
     
124.                                         L=M+1;
     
125.                                 }
     
126.                         else R=M-1;
     
127.                 }
     
128.         ANS.pp();
     
129.         return 0;
     
130. }

复制代码