提交记录 21391
提交时间 |
评测时间 |
2024-03-10 20:58:22 |
2024-03-10 20:58:24 |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool greaterThanOrEqualTo(const vector<int>& remain, int lsdIndex, const vector<int>& divisor) {
if (lsdIndex + divisor.size() - 1 >= remain.size()) {
return false;
}
if (lsdIndex + divisor.size() < remain.size() && remain[lsdIndex + divisor.size()] > 0) {
return true;
}
for (int i = divisor.size() - 1; i >= 0; i--) {
if (remain[lsdIndex + i] > divisor[i]) {
return true;
} else if (remain[lsdIndex + i] < divisor[i]) {
return false;
}
}
return true; // equal
}
void shrinkLeadingZero(vector<int>& number) {
int newSize = number.size();
while (newSize > 1 && number[newSize - 1] == 0) {
--newSize;
}
number.resize(newSize);
}
vector<int> divide(const vector<int>÷nd, const vector<int>& divisor) { // LSD first, no leading zero in the end
vector<int> remain = dividend;
vector<int> quotient(dividend.size());
for (int lsdIndex = remain.size() - 1; lsdIndex >= 0; lsdIndex--) {
while (greaterThanOrEqualTo(remain, lsdIndex, divisor)) {
for (int i = 0; i < divisor.size(); i++) {
remain[lsdIndex + i] -= divisor[i];
if (remain[lsdIndex + i] < 0) {
remain[lsdIndex + i] += 10;
remain[lsdIndex + i + 1]--;
}
}
++quotient[lsdIndex];
}
}
shrinkLeadingZero(quotient);
return quotient;
}
char bigNumBuffer[10010];
vector<int> readBigNum() {
scanf("%s", bigNumBuffer);
vector<int> bigNum;
for (int i = 0; bigNumBuffer[i]; i++) {
bigNum.push_back(bigNumBuffer[i] - '0');
}
reverse(bigNum.begin(), bigNum.end());
shrinkLeadingZero(bigNum);
return bigNum;
}
int main() {
vector<int> dividend = readBigNum();
vector<int> divisor = readBigNum();
vector<int> quotient = divide(dividend, divisor);
for (int i = quotient.size() - 1; i >= 0; i--) {
printf("%d", quotient[i]);
}
puts("");
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 488.148 ms | 236 KB | Accepted | Score: 100 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 10:50:43 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用