← All problems Problem 728
Moves are cyclic shifts of a k-run flip vector over GF(2). The number of solvable states is 2^rank of the circulant generated by 1+x+...+x^(k-1) mod x^n+1, which reduces to F(n,k) = 2^(n-g) if v2(n) < v2(k), else 2^(n-g+1), with g = gcd(n,k). Grouping k by gcd gives S(N) = sum over m*g <= N of (phi(m) + c(m)) * 2^(g*(m-1)), where c(m) counts odd j <= m coprime to m: c(1)=1, c(m)=phi(m) for even m, c(m)=phi(m)/2 for odd m > 1. Computed with a phi sieve and an O(N log N) double loop, all mod 1e9+7.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n log log n)Space complexity O(n)O(n)Approach Flow solution Sieve-based totient computation Verdict Suboptimal
Flow source
# Project Euler 728: Circle of Coins
# Moves are cyclic shifts of a k-run flip vector over GF(2). The number of
# solvable states is 2^rank of the circulant generated by 1+x+...+x^(k-1)
# mod x^n+1, which reduces to F(n,k) = 2^(n-g) if v2(n) < v2(k), else
# 2^(n-g+1), with g = gcd(n,k). Grouping k by gcd gives
# S(N) = sum over m*g <= N of (phi(m) + c(m)) * 2^(g*(m-1)), where c(m)
# counts odd j <= m coprime to m: c(1)=1, c(m)=phi(m) for even m,
# c(m)=phi(m)/2 for odd m > 1. Computed with a phi sieve and an O(N log N)
# double loop, all mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function main() -> i32 {
let big_n: i64 = 10000000
let md: i64 = 1000000007
let phi: ptr<i64> = calloc(big_n + 1, 8) as ptr<i64>
for i in 0..(big_n + 1) {
phi[i] = i
}
for i in 2..(big_n + 1) {
if phi[i] == i {
let mut j: i64 = i
while j <= big_n {
phi[j] = phi[j] - phi[j] / i
j = j + i
}
}
}
let mut total: i64 = 0
let mut base: i64 = 1
for m in 1..(big_n + 1) {
let mut w: i64 = 0
if m == 1 {
w = 2
} else {
if m % 2 == 0 {
w = 2 * phi[m]
} else {
w = phi[m] + phi[m] / 2
}
}
let reps: i64 = big_n / m
let mut cur: i64 = 1
let mut acc: i64 = 0
let mut g: i64 = 0
while g < reps {
cur = cur * base % md
acc = acc + cur
if acc >= md {
acc = acc - md
}
g = g + 1
}
total = (total + w % md * acc) % md
base = base * 2 % md
}
free(phi as ptr<void>)
printf("%lld\n", total)
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 big_n = 10000000;
int64_t md = 1000000007;
int64_t* phi = (int64_t*)(((int64_t*)(calloc((big_n + 1), 8))));
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= (big_n + 1)) ? i < (big_n + 1) : i > (big_n + 1); i += (0 <= (big_n + 1)) ? 1 : -1) {
phi[i] = i;
}
int32_t __flow_step_2 = 1;
for (int32_t i = 2; (2 <= (big_n + 1)) ? i < (big_n + 1) : i > (big_n + 1); i += (2 <= (big_n + 1)) ? 1 : -1) {
if (phi[i] == i) {
int64_t j = i;
while (j <= big_n) {
phi[j] = (phi[j] - FLOW_CHECKED_DIV((phi[j]), (i)));
j = (j + i);
}
}
}
int64_t total = 0;
int64_t base = 1;
int32_t __flow_step_3 = 1;
for (int32_t m = 1; (1 <= (big_n + 1)) ? m < (big_n + 1) : m > (big_n + 1); m += (1 <= (big_n + 1)) ? 1 : -1) {
int64_t w = 0;
if (m == 1) {
w = 2;
} else {
if (FLOW_CHECKED_MOD((m), (2)) == 0) {
w = (2 * phi[m]);
} else {
w = (phi[m] + FLOW_CHECKED_DIV((phi[m]), (2)));
}
}
int64_t reps = FLOW_CHECKED_DIV((big_n), (m));
int64_t cur = 1;
int64_t acc = 0;
int64_t g = 0;
while (g < reps) {
cur = FLOW_CHECKED_MOD(((cur * base)), (md));
acc = (acc + cur);
if (acc >= md) {
acc = (acc - md);
}
g = (g + 1);
}
total = FLOW_CHECKED_MOD(((total + (FLOW_CHECKED_MOD((w), (md)) * acc))), (md));
base = FLOW_CHECKED_MOD(((base * 2)), (md));
}
free(((void*)(phi)));
printf("%lld\n", total);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @main() -> i32 {
%0 = arith.constant 10000000 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 1000000007 : i32
%3 = arith.extsi %2 : i32 to i64
%5 = arith.constant 1 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.addi %1, %7 : i64
%8 = arith.constant 8 : i32
%9 = arith.extsi %8 : i32 to i64
%4 = func.call @calloc(%6, %9) : (i64, i64) -> !llvm.ptr
%10 = arith.constant 0 : i32
%11 = arith.constant 1 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.addi %1, %13 : i64
%14 = arith.index_cast %10 : i32 to index
%15 = arith.index_cast %12 : i32 to index
%17 = arith.constant 1 : index
%18 = arith.constant -1 : index
%19 = arith.cmpi sle, %14, %15 : index
%16 = arith.select %19, %17, %18 : index
cf.br ^bb0(%14 : index)
^bb0(%20: index):
%21 = arith.cmpi slt, %20, %15 : index
%22 = arith.cmpi sgt, %20, %15 : index
%23 = arith.select %19, %21, %22 : i1
cf.cond_br %23, ^bb1(%20 : index), ^bb2(%20 : index)
^bb1(%24: index):
%25 = arith.index_cast %24 : index to i64
%26 = arith.index_cast %24 : index to i64
%27 = llvm.getelementptr %4[%26] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %25, %27 : i64, !llvm.ptr
%28 = arith.addi %24, %16 : index
cf.br ^bb0(%28 : index)
^bb2(%29: index):
%30 = arith.constant 2 : i32
%31 = arith.constant 1 : i32
%33 = arith.extsi %31 : i32 to i64
%32 = arith.addi %1, %33 : i64
%34 = arith.index_cast %30 : i32 to index
%35 = arith.index_cast %32 : i32 to index
%37 = arith.constant 1 : index
%38 = arith.constant -1 : index
%39 = arith.cmpi sle, %34, %35 : index
%36 = arith.select %39, %37, %38 : index
cf.br ^bb3(%34 : index)
^bb3(%40: index):
%41 = arith.cmpi slt, %40, %35 : index
%42 = arith.cmpi sgt, %40, %35 : index
%43 = arith.select %39, %41, %42 : i1
cf.cond_br %43, ^bb4(%40 : index), ^bb5(%40 : index)
^bb4(%44: index):
%46 = arith.index_cast %44 : index to i64
%47 = llvm.getelementptr %4[%46] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%45 = llvm.load %47 : !llvm.ptr -> i64
%49 = arith.trunci %45 : i64 to i32
%50 = arith.index_cast %44 : index to i32
%48 = arith.cmpi eq, %49, %50 : i32
cf.cond_br %48, ^bb6, ^bb7
^bb6:
%51 = arith.index_cast %44 : index to i64
%52 = llvm.mlir.constant(1 : i64) : i64
%53 = llvm.alloca %52 x i64 : (i64) -> !llvm.ptr
llvm.store %51, %53 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%54 = llvm.load %53 : !llvm.ptr -> i64
%55 = arith.cmpi sle, %54, %1 : i64
cf.cond_br %55, ^bb10, ^bb11
^bb10:
%57 = llvm.load %53 : !llvm.ptr -> i64
%58 = llvm.getelementptr %4[%57] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%56 = llvm.load %58 : !llvm.ptr -> i64
%60 = llvm.load %53 : !llvm.ptr -> i64
%61 = llvm.getelementptr %4[%60] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%59 = llvm.load %61 : !llvm.ptr -> i64
%63 = arith.trunci %59 : i64 to i32
%64 = arith.index_cast %44 : index to i32
%62 = arith.divsi %63, %64 : i32
%66 = arith.extsi %62 : i32 to i64
%65 = arith.subi %56, %66 : i64
%67 = llvm.load %53 : !llvm.ptr -> i64
%68 = llvm.getelementptr %4[%67] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %65, %68 : i64, !llvm.ptr
%69 = llvm.load %53 : !llvm.ptr -> i64
%71 = arith.trunci %69 : i64 to i32
%72 = arith.index_cast %44 : index to i32
%70 = arith.addi %71, %72 : i32
%73 = arith.extsi %70 : i32 to i64
llvm.store %73, %53 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%74 = arith.addi %44, %36 : index
cf.br ^bb3(%74 : index)
^bb5(%75: index):
%76 = arith.constant 0 : i32
%77 = arith.extsi %76 : i32 to i64
%78 = llvm.mlir.constant(1 : i64) : i64
%79 = llvm.alloca %78 x i64 : (i64) -> !llvm.ptr
llvm.store %77, %79 : i64, !llvm.ptr
%80 = arith.constant 1 : i32
%81 = arith.extsi %80 : i32 to i64
%82 = llvm.mlir.constant(1 : i64) : i64
%83 = llvm.alloca %82 x i64 : (i64) -> !llvm.ptr
llvm.store %81, %83 : i64, !llvm.ptr
%84 = arith.constant 1 : i32
%85 = arith.constant 1 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.addi %1, %87 : i64
%88 = arith.index_cast %84 : i32 to index
%89 = arith.index_cast %86 : i32 to index
%91 = arith.constant 1 : index
%92 = arith.constant -1 : index
%93 = arith.cmpi sle, %88, %89 : index
%90 = arith.select %93, %91, %92 : index
cf.br ^bb12(%88 : index)
^bb12(%94: index):
%95 = arith.cmpi slt, %94, %89 : index
%96 = arith.cmpi sgt, %94, %89 : index
%97 = arith.select %93, %95, %96 : i1
cf.cond_br %97, ^bb13(%94 : index), ^bb14(%94 : index)
^bb13(%98: index):
%99 = arith.constant 0 : i32
%100 = arith.extsi %99 : i32 to i64
%101 = llvm.mlir.constant(1 : i64) : i64
%102 = llvm.alloca %101 x i64 : (i64) -> !llvm.ptr
llvm.store %100, %102 : i64, !llvm.ptr
%103 = arith.constant 1 : i32
%105 = arith.index_cast %98 : index to i32
%104 = arith.cmpi eq, %105, %103 : i32
cf.cond_br %104, ^bb15, ^bb16
^bb15:
%106 = arith.constant 2 : i32
%107 = arith.extsi %106 : i32 to i64
llvm.store %107, %102 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
%108 = arith.constant 2 : i32
%110 = arith.index_cast %98 : index to i32
%109 = arith.remsi %110, %108 : i32
%111 = arith.constant 0 : i32
%112 = arith.cmpi eq, %109, %111 : i32
cf.cond_br %112, ^bb18, ^bb19
^bb18:
%113 = arith.constant 2 : i32
%115 = arith.index_cast %98 : index to i64
%116 = llvm.getelementptr %4[%115] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%114 = llvm.load %116 : !llvm.ptr -> i64
%118 = arith.extsi %113 : i32 to i64
%117 = arith.muli %118, %114 : i64
llvm.store %117, %102 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
%120 = arith.index_cast %98 : index to i64
%121 = llvm.getelementptr %4[%120] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%119 = llvm.load %121 : !llvm.ptr -> i64
%123 = arith.index_cast %98 : index to i64
%124 = llvm.getelementptr %4[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%122 = llvm.load %124 : !llvm.ptr -> i64
%125 = arith.constant 2 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.divsi %122, %127 : i64
%128 = arith.addi %119, %126 : i64
llvm.store %128, %102 : i64, !llvm.ptr
cf.br ^bb20
^bb20:
cf.br ^bb17
^bb17:
%130 = arith.trunci %1 : i64 to i32
%131 = arith.index_cast %98 : index to i32
%129 = arith.divsi %130, %131 : i32
%132 = arith.extsi %129 : i32 to i64
%133 = arith.constant 1 : i32
%134 = arith.extsi %133 : i32 to i64
%135 = llvm.mlir.constant(1 : i64) : i64
%136 = llvm.alloca %135 x i64 : (i64) -> !llvm.ptr
llvm.store %134, %136 : i64, !llvm.ptr
%137 = arith.constant 0 : i32
%138 = arith.extsi %137 : i32 to i64
%139 = llvm.mlir.constant(1 : i64) : i64
%140 = llvm.alloca %139 x i64 : (i64) -> !llvm.ptr
llvm.store %138, %140 : i64, !llvm.ptr
%141 = arith.constant 0 : i32
%142 = arith.extsi %141 : i32 to i64
%143 = llvm.mlir.constant(1 : i64) : i64
%144 = llvm.alloca %143 x i64 : (i64) -> !llvm.ptr
llvm.store %142, %144 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%145 = llvm.load %144 : !llvm.ptr -> i64
%146 = arith.cmpi slt, %145, %132 : i64
cf.cond_br %146, ^bb22, ^bb23
^bb22:
%147 = llvm.load %136 : !llvm.ptr -> i64
%148 = llvm.load %83 : !llvm.ptr -> i64
%149 = arith.muli %147, %148 : i64
%150 = arith.remsi %149, %3 : i64
llvm.store %150, %136 : i64, !llvm.ptr
%151 = llvm.load %140 : !llvm.ptr -> i64
%152 = llvm.load %136 : !llvm.ptr -> i64
%153 = arith.addi %151, %152 : i64
llvm.store %153, %140 : i64, !llvm.ptr
%154 = llvm.load %140 : !llvm.ptr -> i64
%155 = arith.cmpi sge, %154, %3 : i64
cf.cond_br %155, ^bb24, ^bb25
^bb24:
%156 = llvm.load %140 : !llvm.ptr -> i64
%157 = arith.subi %156, %3 : i64
llvm.store %157, %140 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%158 = llvm.load %144 : !llvm.ptr -> i64
%159 = arith.constant 1 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.addi %158, %161 : i64
llvm.store %160, %144 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%162 = llvm.load %79 : !llvm.ptr -> i64
%163 = llvm.load %102 : !llvm.ptr -> i64
%164 = arith.remsi %163, %3 : i64
%165 = llvm.load %140 : !llvm.ptr -> i64
%166 = arith.muli %164, %165 : i64
%167 = arith.addi %162, %166 : i64
%168 = arith.remsi %167, %3 : i64
llvm.store %168, %79 : i64, !llvm.ptr
%169 = llvm.load %83 : !llvm.ptr -> i64
%170 = arith.constant 2 : i32
%172 = arith.extsi %170 : i32 to i64
%171 = arith.muli %169, %172 : i64
%173 = arith.remsi %171, %3 : i64
llvm.store %173, %83 : i64, !llvm.ptr
%174 = arith.addi %98, %90 : index
cf.br ^bb12(%174 : index)
^bb14(%175: index):
func.call @free(%4) : (!llvm.ptr) -> ()
%177 = llvm.mlir.addressof @str_0 : !llvm.ptr
%178 = llvm.load %79 : !llvm.ptr -> i64
%179 = llvm.call @printf(%177, %178) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%180 = arith.constant 0 : i32
func.return %180 : i32
}
}