/* kwin.c -- job 2774 (route 118). K*(P,S) and its winning window, same object as killer-marginal.py. * * Slots: x in [0,L), L = P*prod(S), with gcd(x,P) = gcd(x+2,P) = 1. x is killed iff x = 0 or -2 (mod s) * for some s in S. K* = maximal cyclic run of consecutive killed slots. The window is the run of length K* * with the smallest first slot; the cyclic wrap run (last run + first run) competes with the start slot of * its last part, so it wins only when strictly longer (arrangement-stats.py winning_window). * * cc -O2 -o kwin kwin.c * ./kwin P s1 s2 ... -> {"P":..,"S":[..],"L":..,"alive":..,"K":..,"first":..} (stdout) */ #include #include #include static uint64_t gcd(uint64_t a, uint64_t b) { while (b) { uint64_t t = a % b; a = b; b = t; } return a; } int main(int argc, char **argv) { if (argc < 3) { fprintf(stderr, "usage: kwin P s1 [s2 ...]\n"); return 2; } uint64_t P = strtoull(argv[1], 0, 10); int ns = argc - 2; uint64_t s[16], L = P; for (int i = 0; i < ns; i++) { s[i] = strtoull(argv[i + 2], 0, 10); L *= s[i]; } /* alive offsets mod P */ uint64_t *off = malloc(sizeof(uint64_t) * P); int no = 0; for (uint64_t r = 0; r < P; r++) if (gcd(r, P) == 1 && gcd(r + 2, P) == 1) off[no++] = r; /* per prime: offset residues and a kill table over [0, 2s) */ uint32_t *om[16]; unsigned char *kt[16]; uint64_t rb[16], step[16]; for (int i = 0; i < ns; i++) { om[i] = malloc(sizeof(uint32_t) * no); for (int j = 0; j < no; j++) om[i][j] = (uint32_t)(off[j] % s[i]); kt[i] = calloc(2 * s[i], 1); for (uint64_t t = 0; t < 2 * s[i]; t++) { uint64_t m = t % s[i]; kt[i][t] = (m == 0 || m == s[i] - 2); } rb[i] = 0; step[i] = P % s[i]; } uint64_t nblocks = L / P, alive = 0; int first_killed = -1; /* is alive index 0 killed */ uint64_t first_len = 0; int first_open = 1; /* length of the run that opens the period */ uint64_t cur = 0, cur_start = 0, best = 0, best_start = 0; for (uint64_t b = 0; b < nblocks; b++) { uint64_t base = b * P; for (int j = 0; j < no; j++) { int k = 0; for (int i = 0; i < ns; i++) if (kt[i][rb[i] + om[i][j]]) { k = 1; break; } if (first_killed < 0) first_killed = k; if (k) { if (cur == 0) cur_start = base + off[j]; cur++; } else { if (first_open) { first_len = cur; first_open = 0; } if (cur > best) { best = cur; best_start = cur_start; } cur = 0; } alive++; } for (int i = 0; i < ns; i++) { rb[i] += step[i]; if (rb[i] >= s[i]) rb[i] -= s[i]; } } uint64_t K, first; if (first_open) { K = alive; first = off[0]; } /* every slot killed (not expected) */ else { if (cur > best) { best = cur; best_start = cur_start; } /* closing run as a linear run */ K = best; first = best_start; if (cur > 0 && first_killed == 1) { /* cyclic wrap: closing run + opening run */ uint64_t w = cur + first_len; if (w > K) { K = w; first = cur_start; } } } printf("{\"P\":%llu,\"S\":[", (unsigned long long)P); for (int i = 0; i < ns; i++) printf(i ? ",%llu" : "%llu", (unsigned long long)s[i]); printf("],\"L\":%llu,\"alive\":%llu,\"K\":%llu,\"first\":%llu}\n", (unsigned long long)L, (unsigned long long)alive, (unsigned long long)K, (unsigned long long)first); return 0; }