代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


/*
 * Divide 10,000 decimal digits by 5,000 decimal digits.  The fixed decimal
 * lengths let us use base 1e9 Knuth division with small, stack-only arrays.
 * On JudgeDuck stdin/stdout are already memory buffers, so no libc I/O or
 * normal C runtime startup is needed.
 */

typedef unsigned int u32;
typedef unsigned long u64;
typedef long i64;

enum {
    BASE = 1000000000u,
    A_LIMBS = 1112,
    B_LIMBS = 556,
    Q_LIMBS = A_LIMBS - B_LIMBS + 1
};

static __attribute__((always_inline)) inline u32 read_dec(const char *p,
                                                           unsigned count) {
    u32 x = 0;
    while (count--) x = x * 10u + (u32)(*p++ - '0');
    return x;
}

static __attribute__((always_inline)) inline char *write_first(char *out,
                                                                u32 x) {
    char buf[10];
    unsigned n = 0;
    do {
        buf[n++] = (char)('0' + x % 10u);
        x /= 10u;
    } while (x);
    while (n) *out++ = buf[--n];
    return out;
}

static __attribute__((always_inline)) inline char *write_nine(char *out,
                                                               u32 x) {
    char *end = out + 9;
    char *p = end;
    do {
        *--p = (char)('0' + x % 10u);
        x /= 10u;
    } while (p != out);
    return end;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *p = info->stdin_ptr;

    /* Big endian limbs.  10,000 = 1 + 1111*9; 5,000 = 5 + 555*9. */
    u32 a[A_LIMBS], v[B_LIMBS], u[A_LIMBS + 1], q[Q_LIMBS];
    a[0] = read_dec(p, 1);
    p += 1;
    for (unsigned i = 1; i < A_LIMBS; ++i, p += 9)
        a[i] = read_dec(p, 9);
    while ((unsigned char)(*p - '0') > 9) ++p;
    v[0] = read_dec(p, 5);
    p += 5;
    for (unsigned i = 1; i < B_LIMBS; ++i, p += 9)
        v[i] = read_dec(p, 9);

    /* Normalize so the divisor's leading limb is at least BASE/2. */
    const u32 d = (u32)((u64)BASE / ((u64)v[0] + 1));
    u64 carry = 0;
    for (unsigned i = B_LIMBS; i-- != 0;) {
        u64 z = (u64)v[i] * d + carry;
        v[i] = (u32)(z % BASE);
        carry = z / BASE;
    }
    carry = 0;
    for (unsigned i = A_LIMBS; i-- != 0;) {
        u64 z = (u64)a[i] * d + carry;
        u[i + 1] = (u32)(z % BASE);
        carry = z / BASE;
    }
    u[0] = (u32)carry;

    for (unsigned j = 0; j < Q_LIMBS; ++j) {
        u64 top = (u64)u[j] * BASE + u[j + 1];
        u64 qhat = top / v[0];
        u64 rhat = top - qhat * v[0];
        while (qhat >= BASE ||
               qhat * v[1] > rhat * BASE + u[j + 2]) {
            --qhat;
            rhat += v[0];
            if (rhat >= BASE) break;
        }

        u64 mul_carry = 0;
        u32 borrow = 0;
#pragma GCC unroll 4
        for (unsigned i = B_LIMBS; i-- != 0;) {
            u64 z = qhat * v[i] + mul_carry;
            mul_carry = z / BASE;
            u32 low = (u32)(z - mul_carry * BASE);
            i64 t = (i64)u[j + i + 1] - low - borrow;
            /* A data-dependent branch here mispredicts roughly half the
             * time on random limbs.  The sign bit is exactly the borrow. */
            u64 negative = (u64)t >> 63;
            u[j + i + 1] = (u32)(t + (i64)(negative * BASE));
            borrow = (u32)negative;
        }
        i64 high = (i64)u[j] - (i64)mul_carry - borrow;
        if (high < 0) {
            --qhat;
            u64 add_carry = 0;
            for (unsigned i = B_LIMBS; i-- != 0;) {
                u64 z = (u64)u[j + i + 1] + v[i] + add_carry;
                if (z >= BASE) {
                    u[j + i + 1] = (u32)(z - BASE);
                    add_carry = 1;
                } else {
                    u[j + i + 1] = (u32)z;
                    add_carry = 0;
                }
            }
            u[j] = (u32)(high + (i64)add_carry);
        } else {
            u[j] = (u32)high;
        }
        q[j] = (u32)qhat;
    }

    unsigned first = 0;
    while (first + 1 < Q_LIMBS && q[first] == 0) ++first;
    char *out = info->stdout_ptr;
    out = write_first(out, q[first++]);
    while (first < Q_LIMBS) out = write_nine(out, q[first++]);
    *out++ = '\n';
    info->stdout_size = (duck_u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果