Solving CF468C: Modulo Constraint with Digit Sum

Define S(x) = Σ_{i=1}^{x} f(i), where f(i) is the sum of digits of i. For a given modulus a ≤ 1e18, we need to find l, r such that S(r) - S(l-1) ≡ 0 (mod a). Observe that shifting the interval by one changes the sum modulo a by one: S(10^18 + k) - S(k) ≡ P + k (mod a), where P = S(10^18) mod a. Therefore, setting k = a - P yields S(10^18 + k) - S(k) ≡ 0 (mod a).

The core is computing P. Use a recursive relation for digit sums:

sum(10^18) = 9 * 10^17 + 2 * sum(10^17)

Expanding yields sum(10^18) = 81 * 10^18. Compute P = (81 * 10^18) mod a using 128-bit integers or modular arithmetic to avoid overflow.

ARC147E: Feasible Examination Set via Difference Prefix Sums

Given pairs (A[i], B[i]), select a subset where A[i] < B[i] for all selected. Sort all A[i] and B[i] in the subset; the condition becomes A_sorted[i] >= B_sorted[i] for all indices. Transform to prefix sums: for any value V, count_{i in S}(B[i] ≤ V) - count_{i in S}(A[i] ≤ V) ≥ 0.

Start by including all i where A[i] < B[i]. Iterate over sorted unique values from a difference map. When the prefix sum becomes negative at some V, we must add some j with B[j] ≤ V < A[j] to balance. Maintain two heaps:

• Min-heap QB ordered by B[j] for unprocessed points.
• Max-heap QA storing A[j] for points with B[j] ≤ current V.

At each deficit, pop from QA and include the point with largest A[j] > V, updating the difference map.

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

const int MAXN = 300005;
map<ll, int> delta;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> byB;
priority_queue<ll> byA;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int total = N, balance = 0;
    for (int i = 0; i < N; ++i) {
        ll x, y; cin >> x >> y;
        if (x < y) {
            delta[y]++; delta[x]--;
            total--;
        } else {
            byB.emplace(y, x);
        }
    }
    for (auto &[val, diff] : delta) {
        balance += diff;
        while (!byB.empty() && byB.top().first <= val) {
            byA.push(byB.top().second);
            byB.pop();
        }
        while (balance < 0) {
            if (byA.empty()) { cout << -1; return 0; }
            if (byA.top() > val) {
                delta[byA.top()]--;
                total--;
                balance++;
            }
            byA.pop();
        }
    }
    cout << total << "\n";
    return 0;
}

AGC027D: Contsructing a Modulo Matrix with LCM

Construct an N×N matrix with distinct positive entries ≤ 1e15, such that each cell equals 1 + LCM(neighbors) mod M for white cells (assuming a checkerboard coloring). Set M=1 to simplify. Assign black cells with products of two distinct primes, ensuring each diagonal uses the same prime factor to control magnitude.

Let primes be indexed. For a black cell at (i,j) where (i+j) is even, assign value prime[diag1[i][j]] * prime[diag2[i][j]]. Define two diagonal mappings: one for NW-SE (diag1) and one for NE-SW (diag2). White cells compute 1 + LCM(adjacent_black_values).

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

const int SZ = 5005;
vector<int> primes;
bool comp[SZ * SZ];

void sieve(int limit) {
    for (int i = 2; i <= limit; ++i) {
        if (!comp[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > limit) break;
            comp[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

ll grid[SZ][SZ];
int diagA[SZ][SZ], diagB[SZ][SZ];

ll computeLCM(ll a, ll b, ll c, ll d) {
    ll res = 1;
    auto update = [&](ll x) { if (x) res = res / __gcd(res, x) * x; };
    update(a); update(b); update(c); update(d);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    if (N == 2) {
        cout << "4 7\n23 10\n";
        return 0;
    }
    sieve(N * N * 2);
    int id = 1;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ((i + j) % 2 == 0) {
                if (diagA[i-1][j-1]) diagA[i][j] = diagA[i-1][j-1];
                else diagA[i][j] = id++;
            }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ((i + j) % 2 == 0) {
                if (diagB[i-1][j+1]) diagB[i][j] = diagB[i-1][j+1];
                else diagB[i][j] = id++;
                grid[i][j] = (ll)primes[diagA[i][j]] * primes[diagB[i][j]];
            }
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ((i + j) % 2 == 1)
                grid[i][j] = computeLCM(grid[i-1][j], grid[i+1][j],
                                         grid[i][j-1], grid[i][j+1]) + 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j)
            cout << grid[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

P7207: Recursive Pairing via Bitwise And Codnition

Given n and m, pair integers from [0, n-1] with [m, m+n-1] such that each pair (x, y) satisfies (x & y) = x. Observe that if we match a suffix of the first set with a prefix of the second set, the condition reduces to (m + len - 1) & (n - 1) = n - 1 for some length len. This condition is both necessary and sufficient because subtraction only affects bits where the higher number has a 1 and the lower has a 0.

Recursive solve: find minimal len > 0 such that (m + len - 1) & (n - len - 1) == n - len - 1. Pair [n-len, n-1] with [m, m+len-1] in reverse order to satisfy the bitwise condition. Then recurse on the remaining prefix [0, n-len-1] and suffix [m+len, m+n-1].

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

void solve(ll n, ll m, ll offset) {
    if (offset == n) return;
    ll suffix_start = n - offset - 1;
    ll prefix_start = m + offset;
    ll match_len = 0;
    for (ll i = prefix_start; i < m + n; ++i) {
        if ((i & suffix_start) == suffix_start) {
            match_len = i - prefix_start + 1;
            break;
        }
    }
    for (ll i = 0; i < match_len; ++i) {
        ll x = suffix_start - (match_len - 1 - i);
        ll y = prefix_start + i;
        cout << x << " " << y << "\n";
    }
    solve(n, m, offset + match_len);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, M; cin >> N >> M;
    solve(N, M, 0);
    return 0;
}