/* kfork.c -- job 2785 (route 127). For one cell (P, p, R): * A = K*(P,R) longest cyclic run of consecutive twin-admissible slots of base P * (r != 0, -2 mod every prime q | P) all killed by R (r = 0 or -2 mod some q in R) * dstar = min over maximal A-runs rho and translates t in Z/p of k_t(rho), where * k_t(rho) = #{r in rho : r + t*M = 0 or -2 mod p}, M = P*prod(R) * F = max over all R-killed runs rho of (|rho| - min_t k_t(rho)) (no-merge floor; B >= F, #1267) * B = K*(P*p,R) by direct scan of the period M*p * Output (stdout, one line): P p A B dstar F nmax R... Timing goes to stderr. * Usage: kfork P p q1 q2 ... (P squarefree with known prime factors <= 7; p prime, p !| P, p not in R) */ #include #include #include #include static int PF[8], nPF, R[16], nR; static int adm(long long r, const int *pf, int npf) { for (int i = 0; i < npf; i++) { long long m = r % pf[i]; if (m == 0 || m == pf[i] - 2) return 0; } return 1; } static int killed(long long r) { for (int i = 0; i < nR; i++) { long long m = r % R[i]; if (m == 0 || m == R[i] - 2) return 1; } return 0; } static long long inv_mod(long long a, long long m) { /* m prime */ long long r = 1, e = m - 2; a %= m; if (a < 0) a += m; while (e) { if (e & 1) r = r * a % m; a = a * a % m; e >>= 1; } return r; } /* longest cyclic killed run over one period of base with prime factors pf */ static long long kstar(long long period, const int *pf, int npf) { long long r0 = -1; for (long long r = 0; r < period; r++) if (adm(r, pf, npf) && !killed(r)) { r0 = r; break; } if (r0 < 0) return -1; long long best = 0, cur = 0; for (long long r = r0 + 1; r <= r0 + period; r++) { if (!adm(r, pf, npf)) continue; if (killed(r)) { if (++cur > best) best = cur; } else cur = 0; } return best; } int main(int argc, char **argv) { if (argc < 4) { fprintf(stderr, "usage: kfork P p q1 q2 ...\n"); return 2; } long long P = atoll(argv[1]); int p = atoi(argv[2]); for (int i = 3; i < argc; i++) R[nR++] = atoi(argv[i]); { long long x = P; for (int q = 2; q <= 7; q++) if (x % q == 0) { PF[nPF++] = q; x /= q; } if (x != 1) { fprintf(stderr, "P factor >7\n"); return 2; } } long long M = P; for (int i = 0; i < nR; i++) M *= R[i]; clock_t c0 = clock(); /* base-P pass: runs, per-run translate fork counts */ long long r0 = -1; for (long long r = 0; r < M; r++) if (adm(r, PF, nPF) && !killed(r)) { r0 = r; break; } if (p == 0) { /* A-only mode */ long long A0 = kstar(M, PF, nPF); printf("%lld 0 %lld", P, A0); for (int i = 0; i < nR; i++) printf(" %d", R[i]); printf("\n"); return 0; } long long Minv = inv_mod(M % p, p); static long long cnt[128]; long long A = 0, F = 0, dstar = 1 << 30, nmax = 0, len = 0, start = 0; /* first pass: A */ for (long long r = r0 + 1, cur = 0; r <= r0 + M; r++) { if (!adm(r, PF, nPF)) continue; if (killed(r)) { if (++cur > A) A = cur; } else cur = 0; } /* second pass: per-run min_t k_t */ len = 0; memset(cnt, 0, sizeof cnt); for (long long r = r0 + 1; r <= r0 + M + 1; r++) { int end = 0; if (r == r0 + M + 1) end = 1; else if (!adm(r, PF, nPF)) continue; else if (killed(r)) { long long rm = r % p; long long t0 = ((p - rm) % p) * Minv % p, t1 = ((2 * p - 2 - rm) % p) * Minv % p; cnt[t0]++; cnt[t1]++; len++; continue; } else end = 1; if (end && len > 0) { long long mn = 1 << 30; for (int t = 0; t < p; t++) if (cnt[t] < mn) mn = cnt[t]; if (len - mn > F) F = len - mn; if (len == A) { nmax++; if (mn < dstar) dstar = mn; } len = 0; memset(cnt, 0, sizeof cnt); } } (void)start; clock_t c1 = clock(); int PF2[9]; int n2 = nPF; memcpy(PF2, PF, sizeof(int) * nPF); PF2[n2++] = p; long long B = kstar(M * p, PF2, n2); clock_t c2 = clock(); printf("%lld %d %lld %lld %lld %lld %lld", P, p, A, B, dstar, F, nmax); for (int i = 0; i < nR; i++) printf(" %d", R[i]); printf("\n"); fprintf(stderr, "M=%lld base %.2fs B %.2fs\n", M, (double)(c1 - c0) / CLOCKS_PER_SEC, (double)(c2 - c1) / CLOCKS_PER_SEC); return 0; }