# Project Euler 410
# F(10^8,10^9)+F(10^9,10^8) lattice points on circles with integer radius constraints.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let R1: i64 = 100000000
let X1: i64 = 1000000000
let R2: i64 = 1000000000
let X2: i64 = 100000000
let limit: i64 = R1
if X2 < limit { limit = X2 }
let n_odd: i64 = limit / 2 + 1
let omega: ptr<i8> = calloc(n_odd, 1)
if omega == null { return 1 }
let mut p: i64 = 3
while p <= limit {
if omega[p >> 1] == 0 {
let step: i64 = p << 1
let mut m: i64 = p
while m <= limit {
omega[m >> 1] = (omega[m >> 1] as i64 + 1) as i8
m = m + step
}
}
p = p + 2
}
let B: i64 = 1024
let num_blocks: i64 = limit / B + 1
let even_pref: ptr<i64> = calloc(num_blocks + 1, 8)
let odd_pref: ptr<i64> = calloc(num_blocks + 1, 8)
if even_pref == null || odd_pref == null { return 1 }
let mut s: i64 = 2
while s <= limit {
# oddpart = s / (s & -s)
let mut ss: i64 = s
while (ss & 1) == 0 { ss = ss >> 1 }
even_pref[s / B + 1] = even_pref[s / B + 1] + (1 << (omega[ss >> 1] as i64))
s = s + 2
}
s = 3
while s <= limit {
let om: i64 = omega[s >> 1] as i64
if om > 0 {
odd_pref[s / B + 1] = odd_pref[s / B + 1] + (1 << (om - 1))
}
s = s + 2
}
let mut i: i64 = 1
while i <= num_blocks {
even_pref[i] = even_pref[i] + even_pref[i - 1]
odd_pref[i] = odd_pref[i] + odd_pref[i - 1]
i = i + 1
}
# Inline F computation twice
let mut total: i64 = 0
let mut pass: i64 = 0
while pass < 2 {
let mut R: i64 = R1
let mut X: i64 = X1
if pass == 1 { R = R2; X = X2 }
let M: i64 = R
if X < M { M = X }
let mut res: i64 = 0
s = 1
while s <= M {
let T: i64 = R / s
let D: i64 = X / s
let mut end: i64 = M
let a: i64 = R / T
let b: i64 = X / D
if a < end { end = a }
if b < end { end = b }
let t_even: i64 = T / 2
let t_odd: i64 = (T + 1) / 2
let odd_count: i64 = (D + 1) / 2
let even_count: i64 = D / 2
let per_a: i64 = 4 * (odd_count * t_odd + even_count * t_even)
let per_b: i64 = 4 * T * D
# sum_even(s,end)
let mut se: i64 = 0
let mut L: i64 = s
let mut RR: i64 = end
if (L & 1) == 1 { L = L + 1 }
if L <= RR {
let bL: i64 = L / B
let bR: i64 = RR / B
if bL == bR {
let mut u: i64 = L
while u <= RR {
let mut oddpart: i64 = u
while (oddpart & 1) == 0 { oddpart = oddpart >> 1 }
se = se + (1 << (omega[oddpart >> 1] as i64))
u = u + 2
}
} else {
se = even_pref[bR] - even_pref[bL + 1]
let mut u2: i64 = L
let lim1: i64 = (bL + 1) * B - 1
while u2 <= lim1 {
let mut oddpart2: i64 = u2
while (oddpart2 & 1) == 0 { oddpart2 = oddpart2 >> 1 }
se = se + (1 << (omega[oddpart2 >> 1] as i64))
u2 = u2 + 2
}
let mut u3: i64 = bR * B
if (u3 & 1) == 1 { u3 = u3 + 1 }
while u3 <= RR {
let mut oddpart3: i64 = u3
while (oddpart3 & 1) == 0 { oddpart3 = oddpart3 >> 1 }
se = se + (1 << (omega[oddpart3 >> 1] as i64))
u3 = u3 + 2
}
}
}
# sum_odd(s,end)
let mut so: i64 = 0
L = s
RR = end
if (L & 1) == 0 { L = L + 1 }
if L <= RR {
let bL2: i64 = L / B
let bR2: i64 = RR / B
if bL2 == bR2 {
let mut u4: i64 = L
while u4 <= RR {
let om4: i64 = omega[u4 >> 1] as i64
if om4 > 0 { so = so + (1 << (om4 - 1)) }
u4 = u4 + 2
}
} else {
so = odd_pref[bR2] - odd_pref[bL2 + 1]
let mut u5: i64 = L
let lim2: i64 = (bL2 + 1) * B - 1
while u5 <= lim2 {
let om5: i64 = omega[u5 >> 1] as i64
if om5 > 0 { so = so + (1 << (om5 - 1)) }
u5 = u5 + 2
}
let mut u6: i64 = bR2 * B
if (u6 & 1) == 0 { u6 = u6 + 1 }
while u6 <= RR {
let om6: i64 = omega[u6 >> 1] as i64
if om6 > 0 { so = so + (1 << (om6 - 1)) }
u6 = u6 + 2
}
}
}
res = res + per_a * se + per_b * so
s = end + 1
}
res = res + 2 * R * X
total = total + res
pass = pass + 1
}
printf("%lld\n", total)
free(odd_pref)
free(even_pref)
free(omega)
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; }
int32_t main(void);
int32_t main(void) {
int64_t R1 = 100000000;
int64_t X1 = 1000000000;
int64_t R2 = 1000000000;
int64_t X2 = 100000000;
int64_t limit = R1;
if (X2 < limit) {
limit = X2;
}
int64_t n_odd = (FLOW_CHECKED_DIV((limit), (2)) + 1);
int8_t* omega = (int8_t*)(calloc(n_odd, 1));
if (omega == NULL) {
return 1;
}
int64_t p = 3;
while (p <= limit) {
if (omega[FLOW_CHECKED_SHR((p), (1))] == 0) {
int64_t step = FLOW_CHECKED_SHL((p), (1));
int64_t m = p;
while (m <= limit) {
omega[FLOW_CHECKED_SHR((m), (1))] = ((int8_t)((((int64_t)(omega[FLOW_CHECKED_SHR((m), (1))])) + 1)));
m = (m + step);
}
}
p = (p + 2);
}
int64_t B = 1024;
int64_t num_blocks = (FLOW_CHECKED_DIV((limit), (B)) + 1);
int64_t* even_pref = (int64_t*)(calloc((num_blocks + 1), 8));
int64_t* odd_pref = (int64_t*)(calloc((num_blocks + 1), 8));
if ((even_pref == NULL || odd_pref == NULL)) {
return 1;
}
int64_t s = 2;
while (s <= limit) {
int64_t ss = s;
while ((ss & 1) == 0) {
ss = FLOW_CHECKED_SHR((ss), (1));
}
even_pref[(FLOW_CHECKED_DIV((s), (B)) + 1)] = (even_pref[(FLOW_CHECKED_DIV((s), (B)) + 1)] + FLOW_CHECKED_SHL((1), (((int64_t)(omega[FLOW_CHECKED_SHR((ss), (1))])))));
s = (s + 2);
}
s = 3;
while (s <= limit) {
int64_t om = ((int64_t)(omega[FLOW_CHECKED_SHR((s), (1))]));
if (om > 0) {
odd_pref[(FLOW_CHECKED_DIV((s), (B)) + 1)] = (odd_pref[(FLOW_CHECKED_DIV((s), (B)) + 1)] + FLOW_CHECKED_SHL((1), ((om - 1))));
}
s = (s + 2);
}
int64_t i = 1;
while (i <= num_blocks) {
even_pref[i] = (even_pref[i] + even_pref[(i - 1)]);
odd_pref[i] = (odd_pref[i] + odd_pref[(i - 1)]);
i = (i + 1);
}
int64_t total = 0;
int64_t pass = 0;
while (pass < 2) {
int64_t R = R1;
int64_t X = X1;
if (pass == 1) {
R = R2;
X = X2;
}
int64_t M = R;
if (X < M) {
M = X;
}
int64_t res = 0;
s = 1;
while (s <= M) {
int64_t T = FLOW_CHECKED_DIV((R), (s));
int64_t D = FLOW_CHECKED_DIV((X), (s));
int64_t end = M;
int64_t a = FLOW_CHECKED_DIV((R), (T));
int64_t b = FLOW_CHECKED_DIV((X), (D));
if (a < end) {
end = a;
}
if (b < end) {
end = b;
}
int64_t t_even = FLOW_CHECKED_DIV((T), (2));
int64_t t_odd = FLOW_CHECKED_DIV(((T + 1)), (2));
int64_t odd_count = FLOW_CHECKED_DIV(((D + 1)), (2));
int64_t even_count = FLOW_CHECKED_DIV((D), (2));
int64_t per_a = (4 * ((odd_count * t_odd) + (even_count * t_even)));
int64_t per_b = ((4 * T) * D);
int64_t se = 0;
int64_t L = s;
int64_t RR = end;
if ((L & 1) == 1) {
L = (L + 1);
}
if (L <= RR) {
int64_t bL = FLOW_CHECKED_DIV((L), (B));
int64_t bR = FLOW_CHECKED_DIV((RR), (B));
if (bL == bR) {
int64_t u = L;
while (u <= RR) {
int64_t oddpart = u;
while ((oddpart & 1) == 0) {
oddpart = FLOW_CHECKED_SHR((oddpart), (1));
}
se = (se + FLOW_CHECKED_SHL((1), (((int64_t)(omega[FLOW_CHECKED_SHR((oddpart), (1))])))));
u = (u + 2);
}
} else {
se = (even_pref[bR] - even_pref[(bL + 1)]);
int64_t u2 = L;
int64_t lim1 = (((bL + 1) * B) - 1);
while (u2 <= lim1) {
int64_t oddpart2 = u2;
while ((oddpart2 & 1) == 0) {
oddpart2 = FLOW_CHECKED_SHR((oddpart2), (1));
}
se = (se + FLOW_CHECKED_SHL((1), (((int64_t)(omega[FLOW_CHECKED_SHR((oddpart2), (1))])))));
u2 = (u2 + 2);
}
int64_t u3 = (bR * B);
if ((u3 & 1) == 1) {
u3 = (u3 + 1);
}
while (u3 <= RR) {
int64_t oddpart3 = u3;
while ((oddpart3 & 1) == 0) {
oddpart3 = FLOW_CHECKED_SHR((oddpart3), (1));
}
se = (se + FLOW_CHECKED_SHL((1), (((int64_t)(omega[FLOW_CHECKED_SHR((oddpart3), (1))])))));
u3 = (u3 + 2);
}
}
}
int64_t so = 0;
L = s;
RR = end;
if ((L & 1) == 0) {
L = (L + 1);
}
if (L <= RR) {
int64_t bL2 = FLOW_CHECKED_DIV((L), (B));
int64_t bR2 = FLOW_CHECKED_DIV((RR), (B));
if (bL2 == bR2) {
int64_t u4 = L;
while (u4 <= RR) {
int64_t om4 = ((int64_t)(omega[FLOW_CHECKED_SHR((u4), (1))]));
if (om4 > 0) {
so = (so + FLOW_CHECKED_SHL((1), ((om4 - 1))));
}
u4 = (u4 + 2);
}
} else {
so = (odd_pref[bR2] - odd_pref[(bL2 + 1)]);
int64_t u5 = L;
int64_t lim2 = (((bL2 + 1) * B) - 1);
while (u5 <= lim2) {
int64_t om5 = ((int64_t)(omega[FLOW_CHECKED_SHR((u5), (1))]));
if (om5 > 0) {
so = (so + FLOW_CHECKED_SHL((1), ((om5 - 1))));
}
u5 = (u5 + 2);
}
int64_t u6 = (bR2 * B);
if ((u6 & 1) == 0) {
u6 = (u6 + 1);
}
while (u6 <= RR) {
int64_t om6 = ((int64_t)(omega[FLOW_CHECKED_SHR((u6), (1))]));
if (om6 > 0) {
so = (so + FLOW_CHECKED_SHL((1), ((om6 - 1))));
}
u6 = (u6 + 2);
}
}
}
res = ((res + (per_a * se)) + (per_b * so));
s = (end + 1);
}
res = (res + ((2 * R) * X));
total = (total + res);
pass = (pass + 1);
}
printf("%lld\n", total);
free(odd_pref);
free(even_pref);
free(omega);
return 0;
}