信息学奥赛一本通 1308. 高精度除法
原题链接
简单
作者:
罚时大师
,
2024-01-21 12:38:25
,
所有人可见
,
阅读 37
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
// Acwing的数据量太大, 超时, 不知信奥网的数据强不强反正过了
#include <bits/stdc++.h>
using namespace std;
vector<int> a, b;
vector<int> ans;
void init(vector<int> &t)
{
string s;
cin >> s;
for (int i = s.size() - 1; i >= 0; i--)
{
t.push_back(s[i] - '0');
}
}
int calc(vector<int> a, vector<int> b)
{
return a.size() - b.size() + 1;
}
vector<int> left_move(vector<int> t, int len)
{
reverse(t.begin(), t.end());
while (len)
{
t.push_back(0);
len--;
}
reverse(t.begin(), t.end());
return t;
}
int max_vec(vector<int> a, vector<int> b)
{
if (a.size() > b.size())
return 1;
if (b.size() > a.size())
return -1;
for (int i = a.size() - 1; i >= 0; i--)
{
if (a[i] > b[i])
return 1;
if (b[i] > a[i])
return -1;
}
return 1;
}
vector<int> sub(vector<int> a, vector<int> b)
{
for (int i = 0; i < max(a.size(), b.size()); i++)
{
if (i < b.size())
{
if (a[i] >= b[i])
a[i] -= b[i];
else
{
a[i + 1]--;
a[i] = a[i] + 10 - b[i];
}
continue;
}
if (a[i] < 0)
{
a[i + 1]--;
a[i] += 10;
}
}
while (a.size() > 1 && !a[a.size() - 1])
a.pop_back();
return a;
}
void output(vector<int> a)
{
reverse(a.begin(), a.end());
while (a.size() > 1 && !a[a.size() - 1])
a.pop_back();
for (int i = a.size() - 1; i >= 0; i--)
{
cout << a[i];
}
cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init(a);
init(b);
vector<int> tmp;
ans.push_back(0); // 商
int len = calc(a, b);
for (int i = len - 1; i >= 0; i--)
{
tmp = b;
int num = 0;
tmp = left_move(tmp, i);
while (max_vec(a, tmp) == 1)
{
num++;
a = sub(a, tmp);
}
ans.push_back(num);
}
output(ans);
reverse(a.begin(), a.end());
output(a);
return 0;
}