题目链接：http://codevs.cn/problem/3118/

为了做一道名为国王游戏的贪心，我跑来学习了高精度除法。。。。相传，高精度除法是高精度四个基本运算最难的

但事实上，高精度除法可以看成其他高精度的组合。。。

我们班一位大佬告诉我，对于高精度除法这类的题，他一直都是二分出这个商，然后高精度乘法来check一下。。。。

当然这是方法之一。。。我在这道题用的方法是高精度减法来做高精度除法

 

【步骤】

1.找到除数与被除数相差的位数并记录下。。。设相差了x位，则除数与被除数的商最大为x+1位数。。。这个结论举个例子就知道了

2.然后我们从x+1位开始做。。让除数扩大10^x倍，变成和被除数相同的位数，然后比较大小，如果能减去就减去，设减去了i次，则商的x+1位为i

在这个地方我们用例子来说明：

3886218：被除数

56322：除数

3886218<56322*100不执行减法操作。。。3886218>56322*100，执行减法，可以减去6个56322*10变成506898

506898>56322,并且可以减去9个56322，变成0 ，所以商就是6*10+9，余数为0

 

说白了，高精度除法就是执行减法，看从被除数中最多可以减去多少个除数，所以高精度除法就是多次高精度减法

高精度除法模板：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define maxn 1005 9 using namespace std;10 11 int a1[maxn],a2[maxn],a3[maxn],a4[maxn];12 int len1,len2;13 char s1[maxn],s2[maxn];14 15 int check(int a[],int b[]){16 if(a[0]
             
              b[0])return 1;18 for(int i=a[0];i>=1;i--){19 if(a[i]>b[i])return 1;20 if(a[i]
              
               1)//余数的位数33 a[0]--;34 }35 36 int main(){37 scanf("%s%s",s1+1,s2+1);38 len1=strlen(s1+1);39 len2=strlen(s2+1);40 for(int i=1;i<=len1;i++)a1[i]=s1[len1-i+1]-'0';41 for(int i=1;i<=len2;i++)a2[i]=s2[len2-i+1]-'0';42 a1[0]=len1;a2[0]=len2;43 a4[0]=len1-len2+1;44 for(int i=a4[0];i>0;i--){45 memset(a3,0,sizeof(a3));46 for(int j=1;j<=a2[0];j++){47 a3[j+i-1]=a2[j];//移i位 48 }49 a3[0]=a2[0]+i-1;50 while(check(a1,a3)){51 a4[i]++;_minus(a1,a3);52 }53 }54 while(a4[a4[0]]==0&&a4[0]>1)//商的位数55 a4[0]--;56 for(int i=a4[0];i>=1;i--){57 printf("%d",a4[i]);58 } 59 /*60 388621861 5632262 out:6963 */64 }