【算法笔记】B1017 A除以B

1017 A除以B （20 分)

 

本题要求计算 A/B ，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。

输入格式：

输入在一行中依次给出 A 和 B，中间以 1 空格分隔。

输出格式：

在一行中依次输出 Q 和 R，中间以 1 空格分隔。

输入样例：

123456789050987654321 7

输出样例：

17636684150141093474 3

codes：

 #include<iostream>

 #include<cstring>

 using namespace std;

 struct num{

     int d[];

     int len;

     num(){

         memset(d, , sizeof(d));

         len = ;

     }

 };

 //先保存数的低位，以便除的时候去掉高位的0

 num change(string s){

     num a;

     a.len = s.size();

     for(int i = ; i < a.len; i++){

         a.d[i] = s[a.len - i - ] - '';

     }

     return a;

 }

 num divide(num a, int b, int& r){

     num c;

     c.len = a.len;

     for(int i = a.len - ; i>=; i--){

         r = r *  + a.d[i];

         if(r < b) c.d[i] = ;//不够除商0

         else{

             c.d[i] = r / b;

             r = r % b;

         }

     }

     //去掉高位的0，只需要长度减小，实际没有删除

     while(c.len -  >=  && c.d[c.len - ] == ){

         c.len--;

     }

     return c;

 }

 void print(num n){

     for(int i = n.len - ; i >= ; i--){

         cout<<n.d[i];

     }

 }

 int main(){

     string str1, str2;

     int b, r = ;

     cin>>str1>>b;

     num a = change(str1);

     print(divide(a, b, r));

     cout<<" "<<r;

     return ;

 }