提交记录 21391


用户 题目 状态 得分 用时 内存 语言 代码长度
xudf6 1005a. 【模板题】高精度除法 Accepted 100 488.148 ms 236 KB C++ 2.02 KB
提交时间 评测时间
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>&dividend, 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;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1488.148 ms236 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-10-05 10:50:43 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用