代码

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
namespace prepare{
    #define mst(it, n) memset(it, n, sizeof it);
    #define pii pair<int, int>
    #define ll long long
    #define rg register
    using namespace std;
    inline void ready(){
        //ios::sync_with_stdio(false);
        //cin.tie(0); cout.tie(0);
        #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        #endif
    }

    inline void rd(int& x){
        x = 0; int f = 0; rg char c = 0;
        while(!isdigit(c)) f |= c == '-', c = getchar();
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        x = f ? -x : x;
    }

    inline void rds(string& s){
        s = ""; rg char c = 0;
        while(!isdigit(c)) c = getchar();
        while(isdigit(c)) s += c, c = getchar();
    }

    inline void wt(rg int x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) wt(x / 10);
        putchar(x % 10 + 48);
    }
}
using namespace prepare;

#define MAXL 1250
const int M = 1000000000;
const int PT[10] = {1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};
int x[MAXL], y[MAXL], ans[MAXL], a[MAXL], b[MAXL];
string s1, s2;

void ini(int* a, string& str){
    int p = str.size();
    if(p == 0) return;
    a[0] = (p + 8) / 9;
    int sum = 0, t = 1, cnt = 9, nxt = 0;
    while(--p, p >= 0){
        sum += (str[p] - '0') * t, t *= 10, --cnt;
        if(!cnt) a[++nxt] = sum, sum = 0, t = 1, cnt = 9;
    }
    a[++nxt] = sum;
}

void pnt(int* a){
    int p = a[0];
    printf("%d", a[p]);
    while(--p, p > 0) printf("%09d", a[p]);
}

inline void setlen(int* a, int p){
    a[0] = p;
    while(!a[a[0]] && a[0] > 1) --a[0];
}


void add(int* a, int* b){
    int ml = max(a[0], b[0]);
    for(int i = 1; i <= ml; ++i){
        a[i] += b[i];
        if(a[i] >= M) a[i] -= M, ++a[i + 1];
    }
    a[0] = a[ml + 1] ? ml + 1 : ml;
}

void sub(int* a, int* b){
    int la = a[0];
    for(int i = 1; i <= la; ++i){
        a[i] -= b[i];
        if(a[i] < 0) a[i] += M, --a[i + 1];
    }
    setlen(a, la);
}

void mul(int* a, int* b, int* c){
    int la = a[0], lb = b[0];
    for(int i = 1; i <= la; ++i)
        for(int j = 1; j <= lb; ++j){
            ll m = 1ll * a[i] * b[j] + c[i + j - 1];
            c[i + j] += m / M, c[i + j - 1] = m % M;
        }
    setlen(c, la + lb);
}

int mod(int* a, int b){
    int ret = 0;
    for(int i = a[0]; i > 0; --i)
        ret = (1ll * ret * M + a[i]) % b;
    return ret;
}

void div(int* a, int b, int* c){
    int res = 0;
    for(int i = a[0]; i > 0; --i){
        ll cur = 1ll * M * res + a[i];
        c[i] = cur / b, res = cur - c[i] * b;
    }
    setlen(c, a[0]);
}

int cmp(int* a, int* b){
    if(a[0] > b[0]) return 1;
    if(a[0] < b[0]) return -1;
    int p = a[0] + 1;
    while(--p, p > 0){
        if(a[p] > b[p]) return 1;
        if(a[p] < b[p]) return -1;
    }
    return 0;
}

void modb(int* a, int* b, int* c){
    int _b[b[0] + 5], la, lb, ha, hb, hca, hcb, s_bit, s_seg = 0;
    _b[0] = c[0] = a[0] + 1;
    lb = b[0], hb = b[lb], hcb = 1;
    while(hb > 9) ++hcb, hb /= 10;
    while(cmp(b, a) != 1){
        la = a[0], ha = a[la], hca = 1;
        int rlb = _b[0] + s_seg;
        if(la < rlb || (la == rlb && ha < _b[_b[0]])){
            mst(_b, 0);
            while(ha > 9) ++hca, ha /= 10;
            s_bit = hca - hcb;
            if(ha < hb) --s_bit;
            if(s_bit < 0) s_bit += 9;
            lb = (hcb + s_bit + (b[0] - 1) * 9 + 8) / 9;
            s_seg = la - lb;
            if(ha < hb && hca == 1) --s_seg;
            _b[0] = lb, _b[1] = (b[1] % PT[s_bit]) * PT[9 - s_bit];
            for(int i = 2; i <= lb; ++i)
                _b[i] = (b[i] % PT[s_bit]) * PT[9 - s_bit] + b[i - 1] / PT[s_bit];
        }

        for(int i = 1; i <= lb; ++i){
            int pa = i + s_seg;
            a[pa] -= _b[i];
            if(a[pa] < 0) a[pa] += M, --a[pa + 1];
            setlen(a, la);
        }
        int pc = s_seg + 1;
        c[pc] += PT[9 - s_bit];
        while(c[pc] >= M) c[pc] -= M, ++c[++pc];
    }
    while(c[0] > 1 && !c[c[0]]) --c[0];
}



int main(){
    ready();
    /*
    rds(s1), rds(s2);
    ini(x, s1), ini(y, s2);
    memcpy(a, x, sizeof a);
    memcpy(b, y, sizeof b);
    add(a, b); pnt(a); putchar('\n');
    memcpy(a, x, sizeof a);
    if(cmp(a, b) == -1){
        putchar('-');
        sub(b, a);
        pnt(b);
    }else{
        sub(a, b);
        pnt(a);
    }
    putchar('\n');
    memcpy(a, x, sizeof a);
    memcpy(b, y, sizeof b);
    mul(a, b, ans);
    pnt(ans); putchar('\n');
    */
    rds(s1), rds(s2);
    ini(a, s1), ini(b, s2);
    modb(a, b, ans);
    pnt(ans);
    return 0;
}

评测结果