1017 A除以B

1017 A除以B

分数 20
作者 CHEN, Yue
单位 浙江大学

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

输入格式：

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

输出格式：

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

输入样例：

123456789050987654321 7
1

输出样例：

17636684150141093474 3
1

代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
C++ (g++)

思路：

本题是高精度除法，直接套板子即可。
高精度除以低精度

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

AC代码：

//高精度除法
#include
using namespace std;
vector<int> A,B;
int main(){
    string a;
    int b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    int t=0;
    for(int i=A.size()-1;i>=0;i--){
        t=t*10+A[i];
        B.push_back(t/b);
        t=t%b;
    }
    reverse(B.begin(),B.end());
    while(B.size()>1&&B.back()==0) B.pop_back();
    for(int i=B.size()-1;i>=0;i--) cout<<B[i];
    cout<<" "<<t<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21