代码

#define DUMPIDX 3
// 1005a: high precision division a / b (a: 10000 digits, b: 5000 digits), floor division.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif

static const unsigned BASE = 1000000000u;
typedef std::vector<unsigned> Big;

static Big tolimbs(const std::string &s) {
    Big v;
    int n = (int)s.size();
    for (int i = n; i > 0; i -= 9) {
        int j = i - 9; if (j < 0) j = 0;
        unsigned x = 0;
        for (int k = j; k < i; k++) x = x * 10 + (unsigned)(s[k] - '0');
        v.push_back(x);
    }
    while (!v.empty() && v.back() == 0) v.pop_back();
    return v;
}

static std::string tostr(const Big &v) {
    if (v.empty()) return "0";
    std::string s = std::to_string(v.back());
    char buf[16];
    for (int i = (int)v.size() - 2; i >= 0; i--) {
        snprintf(buf, sizeof(buf), "%09u", v[i]);
        s += buf;
    }
    return s;
}

static int cmpbig(const Big &a, const Big &b) {
    if (a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
    for (int i = (int)a.size() - 1; i >= 0; i--)
        if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
    return 0;
}

static Big mulsmall(const Big &b, unsigned q) {
    Big r(b.size() + 1, 0);
    unsigned long long carry = 0;
    for (size_t i = 0; i < b.size(); i++) {
        unsigned long long cur = (unsigned long long)b[i] * q + carry;
        r[i] = (unsigned)(cur % BASE);
        carry = cur / BASE;
    }
    r[b.size()] = (unsigned)carry;
    while (!r.empty() && r.back() == 0) r.pop_back();
    return r;
}

static void subbig(Big &a, const Big &b) {
    long long borrow = 0;
    for (size_t i = 0; i < a.size(); i++) {
        long long cur = (long long)a[i] - (i < b.size() ? (long long)b[i] : 0) - borrow;
        if (cur < 0) { cur += BASE; borrow = 1; } else borrow = 0;
        a[i] = (unsigned)cur;
    }
    while (!a.empty() && a.back() == 0) a.pop_back();
}

static std::string divide_dec(const std::string &as, const std::string &bs) {
    Big A = tolimbs(as), B = tolimbs(bs);
    if (B.empty()) return "0";
    if (cmpbig(A, B) < 0) return "0";
    size_t n = A.size();
    Big R, Q(n, 0);
    for (int i = (int)n - 1; i >= 0; i--) {
        R.insert(R.begin(), A[i]);
        while (!R.empty() && R.back() == 0) R.pop_back();
        unsigned lo = 0, hi = BASE - 1, best = 0;
        while (lo <= hi) {
            unsigned mid = lo + ((hi - lo) >> 1);
            Big P = mulsmall(B, mid);
            if (cmpbig(P, R) <= 0) { best = mid; if (mid == BASE - 1) break; lo = mid + 1; }
            else { if (mid == 0) break; hi = mid - 1; }
        }
        Q[i] = best;
        if (best) { Big P = mulsmall(B, best); subbig(R, P); }
    }
    while (!Q.empty() && Q.back() == 0) Q.pop_back();
    return tostr(Q);
}

static char pad[64 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}

int main() {
    static char buf[1 << 20];
    size_t n = fread(buf, 1, sizeof(buf), stdin);
    std::string all(buf, buf + n);
    size_t pos = 0;
    std::string as, bs;
    while (pos < all.size() && (all[pos] < '0' || all[pos] > '9')) pos++;
    while (pos < all.size() && all[pos] >= '0' && all[pos] <= '9') as += all[pos++];
    while (pos < all.size() && (all[pos] < '0' || all[pos] > '9')) pos++;
    while (pos < all.size() && all[pos] >= '0' && all[pos] <= '9') bs += all[pos++];
    std::string ans = divide_dec(as, bs);
    ans += "\n";
    fwrite(ans.data(), 1, ans.size(), stdout);

    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < 4) v = ((unsigned long long)ans.size() >> (8 * (DUMPIDX & 3))) & 0xFF;
        else v = (DUMPIDX - 4 < (int)ans.size()) ? (unsigned char)ans[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

//pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果