Distinct Terms in a Multiplication Table — P(64, 10^16). Partition by maximal divisor d <= m; count r <= n avoiding forbidden divisibility via inclusion-exclusion with LCM pruning + memoization.
# Project Euler 466
# Distinct Terms in a Multiplication Table — P(64, 10^16).
# Partition by maximal divisor d <= m; count r <= n avoiding forbidden
# divisibility via inclusion-exclusion with LCM pruning + memoization.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
let mut G_n: i64 = 0
let mut G_divs: ptr<i64> = null
let mut G_ndiv: i64 = 0
let mut G_memo_k1: ptr<i64> = null
let mut G_memo_k2: ptr<i64> = null
let mut G_memo_v: ptr<i64> = null
let mut G_memo_u: ptr<i8> = null
let mut G_memo_cap: i64 = 4000037
function gcd64(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
if a < 0 { return 0 - a }
return a
}
function memo_clear() -> void {
let mut i: i64 = 0
while i < G_memo_cap {
G_memo_u[i] = 0
i = i + 1
}
}
function ie_count(start: i64, cur: i64) -> i64 {
# Count r in 1..G_n divisible by some G_divs[start..] via IE, given current lcm=cur.
let key1: i64 = start
let key2: i64 = cur
let mut slot: i64 = (key1 * 1315423911 + key2) % G_memo_cap
if slot < 0 { slot = 0 - slot }
while G_memo_u[slot] != 0 {
if G_memo_k1[slot] == key1 && G_memo_k2[slot] == key2 {
return G_memo_v[slot]
}
slot = slot + 1
if slot == G_memo_cap { slot = 0 }
}
let mut total: i64 = 0
let mut i: i64 = start
while i < G_ndiv {
let d: i64 = G_divs[i]
let g: i64 = gcd64(cur, d)
let dg: i64 = d / g
if dg > G_n / cur {
i = i + 1
} else {
let nl: i64 = cur / g * d
total = total + G_n / nl - ie_count(i + 1, nl)
i = i + 1
}
}
G_memo_u[slot] = 1
G_memo_k1[slot] = key1
G_memo_k2[slot] = key2
G_memo_v[slot] = total
return total
}
function build_forbidden(d: i64, m: i64, out: ptr<i64>) -> i64 {
# Collect e/gcd(e,d) for e=d+1..m, then keep minimal under divisibility.
let raw: ptr<i64> = calloc(m + 1, 8)
let mut nraw: i64 = 0
let mut e: i64 = d + 1
while e <= m {
let v: i64 = e / gcd64(e, d)
if v > 1 {
raw[nraw] = v
nraw = nraw + 1
}
e = e + 1
}
# sort ascending (insertion)
let mut i: i64 = 1
while i < nraw {
let key: i64 = raw[i]
let mut j: i64 = i
while j > 0 && raw[j - 1] > key {
raw[j] = raw[j - 1]
j = j - 1
}
raw[j] = key
i = i + 1
}
# unique
let mut nu: i64 = 0
i = 0
while i < nraw {
if nu == 0 || raw[i] != raw[nu - 1] {
raw[nu] = raw[i]
nu = nu + 1
}
i = i + 1
}
# minimal under divisibility
let mut nout: i64 = 0
i = 0
while i < nu {
let x: i64 = raw[i]
let mut red: i64 = 0
let mut k: i64 = 0
while k < nout {
if x % out[k] == 0 {
red = 1
}
k = k + 1
}
if red == 0 {
out[nout] = x
nout = nout + 1
}
i = i + 1
}
free(raw)
# sort descending for better LCM pruning
i = 0
while i < nout {
let mut j: i64 = i + 1
while j < nout {
if out[j] > out[i] {
let tmp: i64 = out[i]
out[i] = out[j]
out[j] = tmp
}
j = j + 1
}
i = i + 1
}
return nout
}
function count_bad(n: i64, divs: ptr<i64>, ndiv: i64) -> i64 {
if ndiv == 0 { return 0 }
G_n = n
G_divs = divs
G_ndiv = ndiv
memo_clear()
return ie_count(0, 1)
}
function P(m: i64, n: i64) -> i64 {
let divs: ptr<i64> = calloc(m + 1, 8)
let mut total: i64 = 0
let mut d: i64 = 1
while d <= m {
let nd: i64 = build_forbidden(d, m, divs)
let bad: i64 = count_bad(n, divs, nd)
total = total + n - bad
d = d + 1
}
free(divs)
return total
}
function main() -> i32 {
G_memo_k1 = calloc(G_memo_cap, 8)
G_memo_k2 = calloc(G_memo_cap, 8)
G_memo_v = calloc(G_memo_cap, 8)
G_memo_u = calloc(G_memo_cap, 1)
if G_memo_k1 == null || G_memo_k2 == null || G_memo_v == null || G_memo_u == null {
return 1
}
printf("%lld\n", P(64, 10000000000000000))
free(G_memo_u)
free(G_memo_v)
free(G_memo_k2)
free(G_memo_k1)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t gcd64_i64_i64(int64_t a0, int64_t b0);
void memo_clear(void);
int64_t ie_count_i64_i64(int64_t start, int64_t cur);
int64_t build_forbidden_i64_i64_ptr_i64(int64_t d, int64_t m, int64_t* out);
int64_t count_bad_i64_ptr_i64_i64(int64_t n, int64_t* divs, int64_t ndiv);
int64_t P_i64_i64(int64_t m, int64_t n);
int32_t main(void);
/* Module statics */
static int64_t G_n = 0;
static int64_t* G_divs = NULL;
static int64_t G_ndiv = 0;
static int64_t* G_memo_k1 = NULL;
static int64_t* G_memo_k2 = NULL;
static int64_t* G_memo_v = NULL;
static int8_t* G_memo_u = NULL;
static int64_t G_memo_cap = 4000037;
int64_t gcd64_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
if (a < 0) {
return (0 - a);
}
return a;
}
void memo_clear(void) {
int64_t i = 0;
while (i < G_memo_cap) {
G_memo_u[i] = 0;
i = (i + 1);
}
}
int64_t ie_count_i64_i64(int64_t start, int64_t cur) {
int64_t key1 = start;
int64_t key2 = cur;
int64_t slot = FLOW_CHECKED_MOD((((key1 * 1315423911) + key2)), (G_memo_cap));
if (slot < 0) {
slot = (0 - slot);
}
while (G_memo_u[slot] != 0) {
if ((G_memo_k1[slot] == key1 && G_memo_k2[slot] == key2)) {
return G_memo_v[slot];
}
slot = (slot + 1);
if (slot == G_memo_cap) {
slot = 0;
}
}
int64_t total = 0;
int64_t i = start;
while (i < G_ndiv) {
int64_t d = G_divs[i];
int64_t g = gcd64_i64_i64(cur, d);
int64_t dg = FLOW_CHECKED_DIV((d), (g));
if (dg > FLOW_CHECKED_DIV((G_n), (cur))) {
i = (i + 1);
} else {
int64_t nl = (FLOW_CHECKED_DIV((cur), (g)) * d);
total = ((total + FLOW_CHECKED_DIV((G_n), (nl))) - ie_count_i64_i64((i + 1), nl));
i = (i + 1);
}
}
G_memo_u[slot] = 1;
G_memo_k1[slot] = key1;
G_memo_k2[slot] = key2;
G_memo_v[slot] = total;
return total;
}
int64_t build_forbidden_i64_i64_ptr_i64(int64_t d, int64_t m, int64_t* out) {
int64_t* raw = (int64_t*)(calloc((m + 1), 8));
int64_t nraw = 0;
int64_t e = (d + 1);
while (e <= m) {
int64_t v = FLOW_CHECKED_DIV((e), (gcd64_i64_i64(e, d)));
if (v > 1) {
raw[nraw] = v;
nraw = (nraw + 1);
}
e = (e + 1);
}
int64_t i = 1;
while (i < nraw) {
int64_t key = raw[i];
int64_t j = i;
while ((j > 0 && raw[(j - 1)] > key)) {
raw[j] = raw[(j - 1)];
j = (j - 1);
}
raw[j] = key;
i = (i + 1);
}
int64_t nu = 0;
i = 0;
while (i < nraw) {
if ((nu == 0 || raw[i] != raw[(nu - 1)])) {
raw[nu] = raw[i];
nu = (nu + 1);
}
i = (i + 1);
}
int64_t nout = 0;
i = 0;
while (i < nu) {
int64_t x = raw[i];
int64_t red = 0;
int64_t k = 0;
while (k < nout) {
if (FLOW_CHECKED_MOD((x), (out[k])) == 0) {
red = 1;
}
k = (k + 1);
}
if (red == 0) {
out[nout] = x;
nout = (nout + 1);
}
i = (i + 1);
}
free(raw);
i = 0;
while (i < nout) {
int64_t j = (i + 1);
while (j < nout) {
if (out[j] > out[i]) {
int64_t tmp = out[i];
out[i] = out[j];
out[j] = tmp;
}
j = (j + 1);
}
i = (i + 1);
}
return nout;
}
int64_t count_bad_i64_ptr_i64_i64(int64_t n, int64_t* divs, int64_t ndiv) {
if (ndiv == 0) {
return 0;
}
G_n = n;
G_divs = divs;
G_ndiv = ndiv;
memo_clear();
return ie_count_i64_i64(0, 1);
}
int64_t P_i64_i64(int64_t m, int64_t n) {
int64_t* divs = (int64_t*)(calloc((m + 1), 8));
int64_t total = 0;
int64_t d = 1;
while (d <= m) {
int64_t nd = build_forbidden_i64_i64_ptr_i64(d, m, divs);
int64_t bad = count_bad_i64_ptr_i64_i64(n, divs, nd);
total = ((total + n) - bad);
d = (d + 1);
}
free(divs);
return total;
}
int32_t main(void) {
G_memo_k1 = calloc(G_memo_cap, 8);
G_memo_k2 = calloc(G_memo_cap, 8);
G_memo_v = calloc(G_memo_cap, 8);
G_memo_u = calloc(G_memo_cap, 1);
if ((((G_memo_k1 == NULL || G_memo_k2 == NULL) || G_memo_v == NULL) || G_memo_u == NULL)) {
return 1;
}
printf("%lld\n", P_i64_i64(64, 10000000000000000));
free(G_memo_u);
free(G_memo_v);
free(G_memo_k2);
free(G_memo_k1);
return 0;
}