Efficient XOR Sum Calculation

Define (f(i) = \oplus_{d|i}d), then compute (\oplus_{i=1}^{n}f(i)) for (n \le 10^{14}).

Approach: Count occurrences of each number via floor division blocks and compute interval XOR sums.

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

ll prefix_xor(ll x) {
    if (!x) return 0;
    ll result = 1;
    if (((x - 1) / 2) & 1) result ^= 1;
    if (!(x & 1)) result ^= x;
    return result;
}

ll range_xor(ll l, ll r) {
    return prefix_xor(r) ^ prefix_xor(l - 1);
}

int main() {
    ll n, ans = 0;
    cin >> n;
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        if ((n / l) & 1) ans ^= range_xor(l, r);
    }
    cout << ans << endl;
    return 0;
}

Graph Path Optimization

Given a graph with (n) nodes and (m) edges, find the optimal meeting point for (k) agents with minimal maximum travel distance.

Solution: Use Dijkstra's algorithm for each agent and evaluate meeting points on both vertices and edges.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, K = 25;

vector<pair<int, int>> adj[N];
ll dist[K][N];
bool vis[N];
int k, ids[K];

void dijkstra(int src) {
    fill(dist[src], dist[src] + N, 1e18);
    fill(vis, vis + N, false);
    priority_queue<pair<ll, int>> pq;
    dist[src][ids[src]] = 0;
    pq.push({0, ids[src]});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (dist[src][v] > dist[src][u] + w) {
                dist[src][v] = dist[src][u] + w;
                pq.push({-dist[src][v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w * 2);
        adj[v].emplace_back(u, w * 2);
    }
    cin >> k;
    ids[0] = 1;
    dijkstra(0);
    for (int i = 1; i <= k; ++i) {
        cin >> ids[i];
        dijkstra(i);
    }
    ll min_max_dist = 1e18;
    for (int i = 1; i <= n; ++i) {
        ll current_max = 0;
        for (int j = 0; j <= k; ++j) {
            current_max = max(current_max, dist[j][i]);
        }
        min_max_dist = min(min_max_dist, current_max);
    }
    cout << min_max_dist << endl;
    return 0;
}

Binary String Manipulation

Given a binary string with segments, maximize the longest non-decreasign subsequence by reversing at most (k) intervals per query.

Constraints: (n \le 2 \times 10^5), (q \le 2 \times 10^5), (0 \le k \le n).