Submission #73914200

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll pow_mod(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int MOD_Q = 10007;
    int K, M;
    cin >> K >> M;
    ll q = 0;
    ll r = 0;
    ll inv_9 = pow_mod(9, MOD_Q - 2, MOD_Q);
    ll inv_M = pow_mod(M, MOD_Q - 2, MOD_Q);
    for (int i = 0; i < K; ++i) {
        char c;
        ll l;
        cin >> c >> l;
        int d = c - '0';
        ll a = 10 % M;
        ll b = d % M;
        ll r_new;
        if (a == 1) {
            r_new = (r + b * l) % M;
        } else {
            ll pow10_l_mod_M = pow_mod(10, l, M);
            ll mod_9M = 9LL * M;
            ll pow10_l_mod_9M = pow_mod(10, l, mod_9M);
            ll numerator = (pow10_l_mod_9M - 1 + mod_9M) % mod_9M;
            ll S_mod_M = (numerator / 9) % M;
            r_new = (pow10_l_mod_M * r % M + b * S_mod_M % M) % M;
        }
        r_new = (r_new + M) % M;
        ll pow10_l_mod_Q = pow_mod(10, l, MOD_Q);
        ll T_numerator = (pow10_l_mod_Q - 1 + MOD_Q) % MOD_Q;
        ll T = T_numerator * inv_9 % MOD_Q;
        ll temp = (1LL * d * T % MOD_Q + 1LL * r * pow10_l_mod_Q % MOD_Q) % MOD_Q;
        temp = (temp - r_new % MOD_Q + MOD_Q) % MOD_Q;
        temp = temp * inv_M % MOD_Q;
        ll q_new = (1LL * q * pow10_l_mod_Q % MOD_Q + temp) % MOD_Q;

        q = q_new;
        r = r_new;
    }
    cout << q % MOD_Q << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Simple Division
User xuhanjin
Language C++23 (GCC 15.2.0)
Score 450
Code Size 1713 Byte
Status AC
Exec Time 58 ms
Memory 3688 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 43
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt
Case Name Status Exec Time Memory
hand_01.txt AC 1 ms 3624 KiB
hand_02.txt AC 1 ms 3580 KiB
hand_03.txt AC 1 ms 3556 KiB
hand_04.txt AC 1 ms 3628 KiB
hand_05.txt AC 1 ms 3488 KiB
sample_01.txt AC 1 ms 3628 KiB
sample_02.txt AC 1 ms 3496 KiB
sample_03.txt AC 1 ms 3528 KiB
test_01.txt AC 1 ms 3488 KiB
test_02.txt AC 54 ms 3604 KiB
test_03.txt AC 54 ms 3660 KiB
test_04.txt AC 55 ms 3496 KiB
test_05.txt AC 55 ms 3556 KiB
test_06.txt AC 55 ms 3416 KiB
test_07.txt AC 56 ms 3592 KiB
test_08.txt AC 55 ms 3492 KiB
test_09.txt AC 56 ms 3496 KiB
test_10.txt AC 56 ms 3496 KiB
test_11.txt AC 56 ms 3460 KiB
test_12.txt AC 56 ms 3440 KiB
test_13.txt AC 56 ms 3688 KiB
test_14.txt AC 56 ms 3484 KiB
test_15.txt AC 55 ms 3660 KiB
test_16.txt AC 56 ms 3624 KiB
test_17.txt AC 57 ms 3496 KiB
test_18.txt AC 57 ms 3440 KiB
test_19.txt AC 56 ms 3496 KiB
test_20.txt AC 56 ms 3628 KiB
test_21.txt AC 56 ms 3644 KiB
test_22.txt AC 56 ms 3660 KiB
test_23.txt AC 56 ms 3440 KiB
test_24.txt AC 55 ms 3492 KiB
test_25.txt AC 56 ms 3488 KiB
test_26.txt AC 56 ms 3624 KiB
test_27.txt AC 56 ms 3496 KiB
test_28.txt AC 56 ms 3628 KiB
test_29.txt AC 56 ms 3624 KiB
test_30.txt AC 58 ms 3496 KiB
test_31.txt AC 57 ms 3688 KiB
test_32.txt AC 56 ms 3416 KiB
test_33.txt AC 56 ms 3688 KiB
test_34.txt AC 55 ms 3496 KiB
test_35.txt AC 55 ms 3496 KiB