lessons/参考实现/10-高斯消元与CRT/AtCoder-agc050_e.cpp

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

constexpr int64 MOD = 998'244'353LL;

int64 lcm_bounded(int64 a, int64 b) {
    return static_cast<int64>(static_cast<i128>(a / gcd(a, b)) * b);
}

int64 prefix_short_part(int64 time, int64 period, int64 remainder) {
    // Count integers t in [0,time) with t mod period < remainder.
    i128 result = static_cast<i128>(time / period) * remainder
                + min(time % period, remainder);
    return static_cast<int64>(result % MOD);
}

int64 sum_weight(int64 left, int64 right, int64 green, int64 period) {
    int64 base = green / period;
    int64 remainder = green % period;
    int64 length = (right - left) % MOD;
    int64 extra = (prefix_short_part(right, period, remainder)
                 - prefix_short_part(left, period, remainder) + MOD) % MOD;
    return (base % MOD * length + extra) % MOD;
}

int64 weight_at(int64 time, int64 green, int64 period) {
    return green / period + (time % period < green % period ? 1 : 0);
}

int64 next_change(int64 time, int64 period, int64 remainder, int64 limit) {
    int64 next = (time / period + 1) * period;
    if (remainder != 0) {
        int64 block = time / period;
        int64 shifted = block * period + remainder;
        if (shifted <= time) ++block;
        if (block < limit / period) shifted = block * period + remainder;
        else shifted = limit;
        next = min(next, shifted);
    }
    return min(next, limit);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    array<int64, 3> green{}, red{}, period{};
    for (int i = 0; i < 3; ++i) {
        cin >> green[i] >> red[i];
        period[i] = green[i] + red[i];
    }

    array<int64, 3> reduced{};
    for (int i = 0; i < 3; ++i) {
        int j = (i + 1) % 3;
        int k = (i + 2) % 3;
        reduced[i] = lcm_bounded(gcd(period[i], period[j]),
                                 gcd(period[i], period[k]));
    }

    i128 reduced_lcm = reduced[0];
    for (int i = 1; i < 3; ++i) {
        reduced_lcm = reduced_lcm / gcd(static_cast<int64>(reduced_lcm % reduced[i]),
                                        reduced[i]) * reduced[i];
    }
    int64 horizon = static_cast<int64>(reduced_lcm);

    int integrated = 0;
    for (int i = 1; i < 3; ++i) {
        if (reduced[i] < reduced[integrated]) integrated = i;
    }
    if (integrated != 0) {
        swap(green[0], green[integrated]);
        swap(period[0], period[integrated]);
        swap(reduced[0], reduced[integrated]);
    }

    int64 compatible_green = 0;
    int64 current = 0;
    while (current < horizon) {
        int64 next = horizon;
        for (int i = 1; i < 3; ++i) {
            next = min(next, next_change(current, reduced[i],
                                         green[i] % reduced[i], horizon));
        }
        int64 other_weights = weight_at(current, green[1], reduced[1]) % MOD;
        other_weights = other_weights * (weight_at(current, green[2], reduced[2]) % MOD) % MOD;
        compatible_green = (compatible_green
                          + other_weights * sum_weight(current, next, green[0], reduced[0])) % MOD;
        current = next;
    }

    int64 common12 = gcd(period[0], period[1]);
    i128 lcm12 = static_cast<i128>(period[0] / common12) * period[1];
    int64 common_with_third = gcd(static_cast<int64>(lcm12 % period[2]), period[2]);
    int64 repetitions = common12 % MOD * (common_with_third % MOD) % MOD;

    cout << compatible_green * repetitions % MOD << '\n';
    return 0;
}