代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace prepare{
    #define mst(it, n) memset(it, n, sizeof it);
    #define pii pair<int, int>
    #define ll long long
    #define rg register
    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;

namespace BigNum{
    #define LL long long
    const int M = 1000000000;//1e9
    const LL MLL = 1000000000LL;
    const int PT[10] = {0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};
    struct BN{
        int d[1200]; int s; BN() {}
        BN& operator=(const BN& bn) {this->s = bn.s; memcpy(this->d, bn.d, sizeof(int) * (this->s + 1)); return *this;}
    };

    void bn_ini(BN& bn, string& s){
        bn.s = -1;
        int len = (int)s.length(); reverse(s.begin(), s.end());
        int cnt = 9, sum = 0, t = 1; int* p = bn.d;
        for(int i = 0; i < len; ++i){
            sum += (s[i] - '0') * t; t *= 10; --cnt;
            if(!cnt || i == len - 1){
                *(p++) = sum; ++bn.s;
                cnt = 9, sum = 0, t = 1;
            }
        }
    }
    void bn_ini(BN& bn, int a){
        bn.s = -1; bn.d[0] = 0;
        if(!a) bn.s = 0;
        while(a) {bn.d[++bn.s] = a % M; a /= M;}
    }
    void bn_ini(BN& bn, LL a){
        bn.s = -1; bn.d[0] = 0;
        if(!a) bn.s = 0;
        while(a) {bn.d[++bn.s] = a % MLL; a /= MLL;}
    }

    int bn_cmp(BN& bn1, BN& bn2){
        if(bn1.s > bn2.s) return 0;
        if(bn1.s < bn2.s) return 1;
        for(int i = bn1.s; i >= 0; --i){
            if(bn1.d[i] > bn2.d[i]) return 0;
            if(bn1.d[i] < bn2.d[i]) return 1;
        }
        return 2;
    }
    int bn_cmp(BN& bn, int& a){
        LL b = bn.d[1] * M + bn.d[0];
        if(bn.s > 1) return 0;
        if(bn.s == 1) return b <= a;
        return bn.d[0] <= a;
    }

    void bn_pnt(BN& bn){
        int s = bn.s;
        wt(bn.d[s--]);
        while(s >= 0){
            int cnt = 10, x = bn.d[s];
            while(x) --cnt, x /= 10;
            while(--cnt) putchar('0');
            x = bn.d[s--]; if(x) wt(x);
        }
    }

    void bn_add(BN& bn1, BN& bn2){
        int c = 0;
        if(bn1.s < bn2.s){
            for(int i = 0; i <= bn1.s; ++i){
            bn1.d[i] = bn1.d[i] + bn2.d[i] + c;
            c = bn1.d[i] / M; bn1.d[i] %= M; 
            }
            for(int i = bn1.s + 1; i <= bn2.s; ++i){
            bn1.d[i] = bn2.d[i] + c;
            c = bn1.d[i] / M; bn1.d[i] %= M; 
            }
            if(c) bn1.d[bn2.s + 1] = 1, bn1.s = bn2.s + 1;
            else bn1.s = bn2.s;
        }else{
            for(int i = 0; i <= bn2.s; ++i){
            bn1.d[i] = bn1.d[i] + bn2.d[i] + c;
            c = bn1.d[i] / M; bn1.d[i] %= M;
            }
            for(int i = bn2.s + 1; i <= bn1.s; ++i){
                bn1.d[i] = bn1.d[i] + c;
                c = bn1.d[i] / M; bn1.d[i] %= M;
                if(!c) break;
            }
            if(c) bn1.d[bn1.s + 1] = 1, ++bn1.s;
        }
    }

    void bn_sub(BN& bn1, BN& bn2){
        int c = 0;
        for(int i = 0; i <= bn2.s; ++i){
            bn1.d[i] = bn1.d[i] - bn2.d[i] - c;
            if(bn1.d[i] < 0) {bn1.d[i] += M; c = 1;}
        }
        for(int i = bn2.s + 1; i <= bn1.s; ++i){
            bn1.d[i] -= c;
            if(bn1.d[i] < 0) bn1.d[i] += M;
            else break;
        }
        for(int i = bn1.s; i > 0; --i) if(bn1.d[i]) {bn1.s = i; return;}
        bn1.s = 0;
    }

    void bn_mul(BN& bn1, BN& bn2, BN& mu){
        BN mut; mut.s = 0; memset(mut.d, 0, sizeof(int) * (bn1.s + bn2.s + 1));
        for(int i = 0; i <= bn1.s; ++i) for(int j = 0; j <= bn2.s; ++j){
            LL m = 1ll * bn1.d[i] * bn2.d[j] + (LL)mut.d[i + j];
            mut.d[i + j + 1] += int(m / MLL), mut.d[i + j] = int(m % MLL);
            /*
            int c = 0;
            while(1){
                LL p = m / MLL, q = m % MLL;
                mut.d[i + j + c] = (int)q;
                if(!p) break; ++c;
                m = (LL)mut.d[i + j + c] + p;
            }
            */
        }
        for(int i = bn1.s + bn2.s + 1; i > 0; --i) if(mut.d[i]) {mut.s = i; mu = mut; return;}
        mut.s = 0; mu = mut;
    }

    void bn_mod(BN& bn1, BN& bn2, BN& di){
        di.s = 0; int sd = bn1.s - bn2.s; bn1.d[bn1.s + 1] = 0;
        if(bn_cmp(bn2, bn1)) memset(di.d, 0, sizeof(int) * (sd + 1));
        else {di.d[0] = 0; return;}
        int l1 = bn1.s * 9, l2 = bn2.s * 9, h1 = bn1.d[bn1.s], h2 = bn2.d[bn2.s];
        while(h1) {++l1; h1 /= 10;}; while(h2) {++l2; h2 /= 10;};
        int sft[bn2.s + 2]; int sc = -1, sm = l1 - l2;
        while(1){
            int s = sm % 9;
            if(sc != s){
                if(!s) {for(int i = 0; i <= bn2.s; ++i) sft[i] = bn2.d[i]; sft[bn2.s + 1] = 0;}
                else{
                    sft[0] = (bn2.d[0] % PT[s]) * PT[9 - s];
                    for(int i = 1; i <= bn2.s; ++i) sft[i] = (bn2.d[i] % PT[s]) * PT[9 - s] + bn2.d[i - 1] / PT[s];
                    sft[bn2.s + 1] = bn2.d[bn2.s] / PT[s];
                }
                sc = s;
            }
            int ds = sm / 9, se = bn2.s + ds + 2, c = 0, no = 0;
            for(int i = se - 1; i >= ds; --i){
                if(bn1.d[i] > sft[i - ds]) {no = 0; break;}
                if(bn1.d[i] < sft[i - ds]) {no = 1; break;}
            }
            if(no) {--sm; continue;}
            for(int i = ds; i < se; ++i){
                bn1.d[i] = bn1.d[i] - sft[i - ds] - c;
                if(bn1.d[i] < 0) {bn1.d[i] += M; c = 1;}
            }
            int k = bn1.s + 1; bn1.s = 0; while(--k) if(bn1.d[k]) {bn1.s = k; break;}
            c = 0; k = sm / 9; di.d[k] += PT[9 - sm % 9];
            for(int i = k; ; ++i){
                c = di.d[k] / M; di.d[k] %= M;
                if(c) ++di.d[i + 1];
                else break;
            }
            if(di.d[sd]) di.s = sd; else di.s = sd - 1; 
            if(!bn_cmp(bn2, bn1)) break;
        }
    }
}
using namespace BigNum;

int main(){
    ready();
    string s1, s2;
    rds(s1), rds(s2);
    BN a, b, c;
    bn_ini(a, s1), bn_ini(b, s2);
    bn_mod(a, b, c);
    bn_pnt(c);

    return 0;
}

评测结果