Method: F(N) decomposes over digit pairs. Stream the digits of all primes below 10^8 (zeros skipped) left to right, keeping W[v] = weighted count of earlier positions whose chosen divisor is v, scaled by the product of the divisor counts of every other processed position. At each digit d with divisor set D and cnt = |D|: ans = ans*cnt + sum over y in D of sum_{x > y} W[x], then W[v] = W[v]*cnt (+ P for v in D), P = P*cnt. Primes come from an odd-only byte sieve of size 10^8. All arithmetic modulo 1e9+7.
# Project Euler 705: Total Inversion Count of Divided Sequences
# Method: F(N) decomposes over digit pairs. Stream the digits of all primes
# below 10^8 (zeros skipped) left to right, keeping W[v] = weighted count of
# earlier positions whose chosen divisor is v, scaled by the product of the
# divisor counts of every other processed position. At each digit d with
# divisor set D and cnt = |D|: ans = ans*cnt + sum over y in D of
# sum_{x > y} W[x], then W[v] = W[v]*cnt (+ P for v in D), P = P*cnt.
# Primes come from an odd-only byte sieve of size 10^8. All arithmetic
# modulo 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let MOD: i64 = 1000000007
let N: i64 = 100000000
# comp[i] marks odd number 2*i+1 as composite (index 0 -> 1, unused)
let half: i64 = N / 2
let comp: ptr<i8> = calloc(half, 1) as ptr<i8>
let mut i: i64 = 1
while (2 * i + 1) * (2 * i + 1) < N {
if comp[i] == 0 {
let p: i64 = 2 * i + 1
let mut j: i64 = (p * p) / 2
while j < half {
comp[j] = 1
j = j + p
}
}
i = i + 1
}
# divisor sets per digit: bitmask over values 1..9, and counts
let dmask: ptr<i64> = calloc(10, 8) as ptr<i64>
let dcnt: ptr<i64> = calloc(10, 8) as ptr<i64>
let mut d: i64 = 1
while d <= 9 {
let mut m: i64 = 0
let mut c: i64 = 0
let mut v: i64 = 1
while v <= d {
if d % v == 0 {
m = m + (1 << v)
c = c + 1
}
v = v + 1
}
dmask[d] = m
dcnt[d] = c
d = d + 1
}
let W: ptr<i64> = calloc(10, 8) as ptr<i64>
let digs: ptr<i64> = calloc(16, 8) as ptr<i64>
let mut P: i64 = 1
let mut ans: i64 = 0
let mut prime: i64 = 2
while prime < N {
# extract nonzero digits of prime, most significant first
let mut nd: i64 = 0
let mut t: i64 = prime
while t > 0 {
let dig: i64 = t % 10
if dig != 0 {
digs[nd] = dig
nd = nd + 1
}
t = t / 10
}
let mut k: i64 = nd - 1
while k >= 0 {
let dg: i64 = digs[k]
let mask: i64 = dmask[dg]
let cnt: i64 = dcnt[dg]
# add = sum over y in divs(dg) of sum_{x > y} W[x]
let mut add: i64 = 0
let mut suf: i64 = 0
let mut v: i64 = 9
while v >= 1 {
# before including W[v], suf = sum_{x > v} W[x]
if (mask / (1 << v)) % 2 == 1 {
add = (add + suf) % MOD
}
suf = (suf + W[v]) % MOD
v = v - 1
}
ans = (ans * cnt + add) % MOD
v = 1
while v <= 9 {
W[v] = (W[v] * cnt) % MOD
v = v + 1
}
v = 1
while v <= 9 {
if (mask / (1 << v)) % 2 == 1 {
W[v] = (W[v] + P) % MOD
}
v = v + 1
}
P = (P * cnt) % MOD
k = k - 1
}
# advance to next prime
if prime == 2 {
prime = 3
} else {
let mut idx: i64 = prime / 2 + 1
while idx < half && comp[idx] == 1 {
idx = idx + 1
}
if idx >= half {
prime = N
} else {
prime = 2 * idx + 1
}
}
}
free(comp as ptr<void>)
free(dmask as ptr<void>)
free(dcnt as ptr<void>)
free(W as ptr<void>)
free(digs as ptr<void>)
printf("%lld\n", ans)
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 MOD = 1000000007;
int64_t N = 100000000;
int64_t half = FLOW_CHECKED_DIV((N), (2));
int8_t* comp = (int8_t*)(((int8_t*)(calloc(half, 1))));
int64_t i = 1;
while ((((2 * i) + 1) * ((2 * i) + 1)) < N) {
if (comp[i] == 0) {
int64_t p = ((2 * i) + 1);
int64_t j = FLOW_CHECKED_DIV(((p * p)), (2));
while (j < half) {
comp[j] = 1;
j = (j + p);
}
}
i = (i + 1);
}
int64_t* dmask = (int64_t*)(((int64_t*)(calloc(10, 8))));
int64_t* dcnt = (int64_t*)(((int64_t*)(calloc(10, 8))));
int64_t d = 1;
while (d <= 9) {
int64_t m = 0;
int64_t c = 0;
int64_t v = 1;
while (v <= d) {
if (FLOW_CHECKED_MOD((d), (v)) == 0) {
m = (m + FLOW_CHECKED_SHL((1), (v)));
c = (c + 1);
}
v = (v + 1);
}
dmask[d] = m;
dcnt[d] = c;
d = (d + 1);
}
int64_t* W = (int64_t*)(((int64_t*)(calloc(10, 8))));
int64_t* digs = (int64_t*)(((int64_t*)(calloc(16, 8))));
int64_t P = 1;
int64_t ans = 0;
int64_t prime = 2;
while (prime < N) {
int64_t nd = 0;
int64_t t = prime;
while (t > 0) {
int64_t dig = FLOW_CHECKED_MOD((t), (10));
if (dig != 0) {
digs[nd] = dig;
nd = (nd + 1);
}
t = FLOW_CHECKED_DIV((t), (10));
}
int64_t k = (nd - 1);
while (k >= 0) {
int64_t dg = digs[k];
int64_t mask = dmask[dg];
int64_t cnt = dcnt[dg];
int64_t add = 0;
int64_t suf = 0;
int64_t v = 9;
while (v >= 1) {
if (FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((mask), (FLOW_CHECKED_SHL((1), (v))))), (2)) == 1) {
add = FLOW_CHECKED_MOD(((add + suf)), (MOD));
}
suf = FLOW_CHECKED_MOD(((suf + W[v])), (MOD));
v = (v - 1);
}
ans = FLOW_CHECKED_MOD((((ans * cnt) + add)), (MOD));
v = 1;
while (v <= 9) {
W[v] = FLOW_CHECKED_MOD(((W[v] * cnt)), (MOD));
v = (v + 1);
}
v = 1;
while (v <= 9) {
if (FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((mask), (FLOW_CHECKED_SHL((1), (v))))), (2)) == 1) {
W[v] = FLOW_CHECKED_MOD(((W[v] + P)), (MOD));
}
v = (v + 1);
}
P = FLOW_CHECKED_MOD(((P * cnt)), (MOD));
k = (k - 1);
}
if (prime == 2) {
prime = 3;
} else {
int64_t idx = (FLOW_CHECKED_DIV((prime), (2)) + 1);
while ((idx < half && comp[idx] == 1)) {
idx = (idx + 1);
}
if (idx >= half) {
prime = N;
} else {
prime = ((2 * idx) + 1);
}
}
}
free(((void*)(comp)));
free(((void*)(dmask)));
free(((void*)(dcnt)));
free(((void*)(W)));
free(((void*)(digs)));
printf("%lld\n", ans);
return 0;
}