← All problems Problem 860
Count fair arrangements of 9898 stacks mod 989898989.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 860 - Gold and Silver Coin Game
# Count fair arrangements of 9898 stacks mod 989898989.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function malloc(n: i64) -> ptr<void>
}
const MOD: i64 = 989898989
const N: i64 = 9898
function modinv(a: i64, mod: i64) -> i64 {
let mut x: i64 = a % mod
if x < 0 {
x = x + mod
}
let mut t0: i64 = 0
let mut t1: i64 = 1
let mut r0: i64 = mod
let mut r1: i64 = x
while r1 != 0 {
let q: i64 = r0 / r1
let tmp_r: i64 = r0 - q * r1
r0 = r1
r1 = tmp_r
let tmp_t: i64 = t0 - q * t1
t0 = t1
t1 = tmp_t
}
return t0 % mod
}
function main() -> i32 {
let fac: ptr<i64> = malloc((N + 1) * 8) as ptr<i64>
let inv_fac: ptr<i64> = malloc((N + 1) * 8) as ptr<i64>
fac[0] = 1
let mut i: i64 = 1
while i <= N {
fac[i] = fac[i - 1] * i % MOD
i = i + 1
}
inv_fac[N] = modinv(fac[N], MOD)
i = N
while i >= 1 {
inv_fac[i - 1] = inv_fac[i] * i % MOD
i = i - 1
}
let fac_n: i64 = fac[N]
let mut total: i64 = 0
let mut t: i64 = 0
while t <= N {
let s: i64 = N - t
if s % 2 == 1 {
t = t + 1
continue
}
let choose_nt: i64 = ((fac_n * inv_fac[t] % MOD) * inv_fac[s]) % MOD
let mut high: i64 = t
if t > s / 4 {
high = s / 4
}
let parity: i64 = t % 2
let mut inner: i64 = 0
let fac_t: i64 = fac[t]
let fac_s: i64 = fac[s]
let mut m: i64 = parity
while m <= high {
let k: i64 = (t + m) / 2
let r: i64 = (s - 4 * m) / 2
let ct: i64 = ((fac_t * inv_fac[k] % MOD) * inv_fac[t - k]) % MOD
let cs: i64 = ((fac_s * inv_fac[r] % MOD) * inv_fac[s - r]) % MOD
let term: i64 = ct * cs % MOD
if m == 0 {
inner = inner + term
} else {
inner = inner + term * 2
}
m = m + 2
}
total = (total + choose_nt * (inner % MOD)) % MOD
t = t + 1
}
printf("%lld\n", total)
free(fac as ptr<void>)
free(inv_fac as ptr<void>)
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 modinv_i64_i64(int64_t a, int64_t mod);
int32_t main(void);
static const int64_t MOD = 989898989;
static const int64_t N = 9898;
int64_t modinv_i64_i64(int64_t a, int64_t mod) {
int64_t x = FLOW_CHECKED_MOD((a), (mod));
if (x < 0) {
x = (x + mod);
}
int64_t t0 = 0;
int64_t t1 = 1;
int64_t r0 = mod;
int64_t r1 = x;
while (r1 != 0) {
int64_t q = FLOW_CHECKED_DIV((r0), (r1));
int64_t tmp_r = (r0 - (q * r1));
r0 = r1;
r1 = tmp_r;
int64_t tmp_t = (t0 - (q * t1));
t0 = t1;
t1 = tmp_t;
}
return FLOW_CHECKED_MOD((t0), (mod));
}
int32_t main(void) {
int64_t* fac = (int64_t*)(((int64_t*)(malloc(((N + 1) * 8)))));
int64_t* inv_fac = (int64_t*)(((int64_t*)(malloc(((N + 1) * 8)))));
fac[0] = 1;
int64_t i = 1;
while (i <= N) {
fac[i] = FLOW_CHECKED_MOD(((fac[(i - 1)] * i)), (MOD));
i = (i + 1);
}
inv_fac[N] = modinv_i64_i64(fac[N], MOD);
i = N;
while (i >= 1) {
inv_fac[(i - 1)] = FLOW_CHECKED_MOD(((inv_fac[i] * i)), (MOD));
i = (i - 1);
}
int64_t fac_n = fac[N];
int64_t total = 0;
int64_t t = 0;
while (t <= N) {
int64_t s = (N - t);
if (FLOW_CHECKED_MOD((s), (2)) == 1) {
t = (t + 1);
continue;
}
int64_t choose_nt = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((fac_n * inv_fac[t])), (MOD)) * inv_fac[s])), (MOD));
int64_t high = t;
if (t > FLOW_CHECKED_DIV((s), (4))) {
high = FLOW_CHECKED_DIV((s), (4));
}
int64_t parity = FLOW_CHECKED_MOD((t), (2));
int64_t inner = 0;
int64_t fac_t = fac[t];
int64_t fac_s = fac[s];
int64_t m = parity;
while (m <= high) {
int64_t k = FLOW_CHECKED_DIV(((t + m)), (2));
int64_t r = FLOW_CHECKED_DIV(((s - (4 * m))), (2));
int64_t ct = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((fac_t * inv_fac[k])), (MOD)) * inv_fac[(t - k)])), (MOD));
int64_t cs = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((fac_s * inv_fac[r])), (MOD)) * inv_fac[(s - r)])), (MOD));
int64_t term = FLOW_CHECKED_MOD(((ct * cs)), (MOD));
if (m == 0) {
inner = (inner + term);
} else {
inner = (inner + (term * 2));
}
m = (m + 2);
}
total = FLOW_CHECKED_MOD(((total + (choose_nt * FLOW_CHECKED_MOD((inner), (MOD))))), (MOD));
t = (t + 1);
}
printf("%lld\n", total);
free(((void*)(fac)));
free(((void*)(inv_fac)));
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 private @malloc(i64) -> !llvm.ptr
// Constant: MOD
llvm.mlir.global internal constant @MOD(989898989 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(9898 : i64) : i64
func.func @modinv(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.remsi %arg0, %arg1 : i64
%1 = llvm.mlir.constant(1 : i64) : i64
%2 = llvm.alloca %1 x i64 : (i64) -> !llvm.ptr
llvm.store %0, %2 : i64, !llvm.ptr
%3 = llvm.load %2 : !llvm.ptr -> i64
%4 = arith.constant 0 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.cmpi slt, %3, %6 : i64
cf.cond_br %5, ^bb0, ^bb1
^bb0:
%7 = llvm.load %2 : !llvm.ptr -> i64
%8 = arith.addi %7, %arg1 : i64
llvm.store %8, %2 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%9 = arith.constant 0 : i32
%10 = arith.extsi %9 : i32 to i64
%11 = llvm.mlir.constant(1 : i64) : i64
%12 = llvm.alloca %11 x i64 : (i64) -> !llvm.ptr
llvm.store %10, %12 : i64, !llvm.ptr
%13 = arith.constant 1 : i32
%14 = arith.extsi %13 : i32 to i64
%15 = llvm.mlir.constant(1 : i64) : i64
%16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
llvm.store %14, %16 : i64, !llvm.ptr
%17 = llvm.mlir.constant(1 : i64) : i64
%18 = llvm.alloca %17 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %18 : i64, !llvm.ptr
%19 = llvm.load %2 : !llvm.ptr -> i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%22 = llvm.load %21 : !llvm.ptr -> i64
%23 = arith.constant 0 : i32
%25 = arith.extsi %23 : i32 to i64
%24 = arith.cmpi ne, %22, %25 : i64
cf.cond_br %24, ^bb4, ^bb5
^bb4:
%26 = llvm.load %18 : !llvm.ptr -> i64
%27 = llvm.load %21 : !llvm.ptr -> i64
%28 = arith.divsi %26, %27 : i64
%29 = llvm.load %18 : !llvm.ptr -> i64
%30 = llvm.load %21 : !llvm.ptr -> i64
%31 = arith.muli %28, %30 : i64
%32 = arith.subi %29, %31 : i64
%33 = llvm.load %21 : !llvm.ptr -> i64
llvm.store %33, %18 : i64, !llvm.ptr
llvm.store %32, %21 : i64, !llvm.ptr
%34 = llvm.load %12 : !llvm.ptr -> i64
%35 = llvm.load %16 : !llvm.ptr -> i64
%36 = arith.muli %28, %35 : i64
%37 = arith.subi %34, %36 : i64
%38 = llvm.load %16 : !llvm.ptr -> i64
llvm.store %38, %12 : i64, !llvm.ptr
llvm.store %37, %16 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%39 = llvm.load %12 : !llvm.ptr -> i64
%40 = arith.remsi %39, %arg1 : i64
func.return %40 : i64
}
func.func @main() -> i32 {
%42 = llvm.mlir.addressof @N : !llvm.ptr
%43 = llvm.load %42 : !llvm.ptr -> i64
%44 = arith.constant 1 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.addi %43, %46 : i64
%47 = arith.constant 8 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.muli %45, %49 : i64
%41 = func.call @malloc(%48) : (i64) -> !llvm.ptr
%51 = llvm.mlir.addressof @N : !llvm.ptr
%52 = llvm.load %51 : !llvm.ptr -> i64
%53 = arith.constant 1 : i32
%55 = arith.extsi %53 : i32 to i64
%54 = arith.addi %52, %55 : i64
%56 = arith.constant 8 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.muli %54, %58 : i64
%50 = func.call @malloc(%57) : (i64) -> !llvm.ptr
%59 = arith.constant 1 : i32
%60 = arith.constant 0 : i32
%61 = arith.extsi %59 : i32 to i64
%62 = arith.extsi %60 : i32 to i64
%63 = llvm.getelementptr %41[%62] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %61, %63 : i64, !llvm.ptr
%64 = arith.constant 1 : i32
%65 = arith.extsi %64 : i32 to i64
%66 = llvm.mlir.constant(1 : i64) : i64
%67 = llvm.alloca %66 x i64 : (i64) -> !llvm.ptr
llvm.store %65, %67 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = llvm.mlir.addressof @N : !llvm.ptr
%70 = llvm.load %69 : !llvm.ptr -> i64
%71 = arith.cmpi sle, %68, %70 : i64
cf.cond_br %71, ^bb7, ^bb8
^bb7:
%73 = llvm.load %67 : !llvm.ptr -> i64
%74 = arith.constant 1 : i32
%76 = arith.extsi %74 : i32 to i64
%75 = arith.subi %73, %76 : i64
%77 = llvm.getelementptr %41[%75] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%72 = llvm.load %77 : !llvm.ptr -> i64
%78 = llvm.load %67 : !llvm.ptr -> i64
%79 = arith.muli %72, %78 : i64
%80 = llvm.mlir.addressof @MOD : !llvm.ptr
%81 = llvm.load %80 : !llvm.ptr -> i64
%82 = arith.remsi %79, %81 : i64
%83 = llvm.load %67 : !llvm.ptr -> i64
%84 = llvm.getelementptr %41[%83] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %82, %84 : i64, !llvm.ptr
%85 = llvm.load %67 : !llvm.ptr -> i64
%86 = arith.constant 1 : i32
%88 = arith.extsi %86 : i32 to i64
%87 = arith.addi %85, %88 : i64
llvm.store %87, %67 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%91 = llvm.mlir.addressof @N : !llvm.ptr
%92 = llvm.load %91 : !llvm.ptr -> i64
%93 = llvm.getelementptr %41[%92] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%90 = llvm.load %93 : !llvm.ptr -> i64
%94 = llvm.mlir.addressof @MOD : !llvm.ptr
%95 = llvm.load %94 : !llvm.ptr -> i64
%89 = func.call @modinv(%90, %95) : (i64, i64) -> i64
%96 = llvm.mlir.addressof @N : !llvm.ptr
%97 = llvm.load %96 : !llvm.ptr -> i64
%98 = llvm.getelementptr %50[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %89, %98 : i64, !llvm.ptr
%99 = llvm.mlir.addressof @N : !llvm.ptr
%100 = llvm.load %99 : !llvm.ptr -> i64
llvm.store %100, %67 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%101 = llvm.load %67 : !llvm.ptr -> i64
%102 = arith.constant 1 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sge, %101, %104 : i64
cf.cond_br %103, ^bb10, ^bb11
^bb10:
%106 = llvm.load %67 : !llvm.ptr -> i64
%107 = llvm.getelementptr %50[%106] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%105 = llvm.load %107 : !llvm.ptr -> i64
%108 = llvm.load %67 : !llvm.ptr -> i64
%109 = arith.muli %105, %108 : i64
%110 = llvm.mlir.addressof @MOD : !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i64
%112 = arith.remsi %109, %111 : i64
%113 = llvm.load %67 : !llvm.ptr -> i64
%114 = arith.constant 1 : i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.subi %113, %116 : i64
%117 = llvm.getelementptr %50[%115] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %112, %117 : i64, !llvm.ptr
%118 = llvm.load %67 : !llvm.ptr -> i64
%119 = arith.constant 1 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.subi %118, %121 : i64
llvm.store %120, %67 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%123 = llvm.mlir.addressof @N : !llvm.ptr
%124 = llvm.load %123 : !llvm.ptr -> i64
%125 = llvm.getelementptr %41[%124] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%122 = llvm.load %125 : !llvm.ptr -> i64
%126 = arith.constant 0 : i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.mlir.constant(1 : i64) : i64
%129 = llvm.alloca %128 x i64 : (i64) -> !llvm.ptr
llvm.store %127, %129 : i64, !llvm.ptr
%130 = arith.constant 0 : i32
%131 = arith.extsi %130 : i32 to i64
%132 = llvm.mlir.constant(1 : i64) : i64
%133 = llvm.alloca %132 x i64 : (i64) -> !llvm.ptr
llvm.store %131, %133 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%134 = llvm.load %133 : !llvm.ptr -> i64
%135 = llvm.mlir.addressof @N : !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> i64
%137 = arith.cmpi sle, %134, %136 : i64
cf.cond_br %137, ^bb13, ^bb14
^bb13:
%138 = llvm.mlir.addressof @N : !llvm.ptr
%139 = llvm.load %138 : !llvm.ptr -> i64
%140 = llvm.load %133 : !llvm.ptr -> i64
%141 = arith.subi %139, %140 : i64
%142 = arith.constant 2 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.remsi %141, %144 : i64
%145 = arith.constant 1 : i32
%147 = arith.extsi %145 : i32 to i64
%146 = arith.cmpi eq, %143, %147 : i64
cf.cond_br %146, ^bb15, ^bb16
^bb15:
%148 = llvm.load %133 : !llvm.ptr -> i64
%149 = arith.constant 1 : i32
%151 = arith.extsi %149 : i32 to i64
%150 = arith.addi %148, %151 : i64
llvm.store %150, %133 : i64, !llvm.ptr
cf.br ^bb12
^bb16:
cf.br ^bb17
^bb17:
%153 = llvm.load %133 : !llvm.ptr -> i64
%154 = llvm.getelementptr %50[%153] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%152 = llvm.load %154 : !llvm.ptr -> i64
%155 = arith.muli %122, %152 : i64
%156 = llvm.mlir.addressof @MOD : !llvm.ptr
%157 = llvm.load %156 : !llvm.ptr -> i64
%158 = arith.remsi %155, %157 : i64
%160 = llvm.getelementptr %50[%141] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%159 = llvm.load %160 : !llvm.ptr -> i64
%161 = arith.muli %158, %159 : i64
%162 = llvm.mlir.addressof @MOD : !llvm.ptr
%163 = llvm.load %162 : !llvm.ptr -> i64
%164 = arith.remsi %161, %163 : i64
%165 = llvm.load %133 : !llvm.ptr -> i64
%166 = llvm.mlir.constant(1 : i64) : i64
%167 = llvm.alloca %166 x i64 : (i64) -> !llvm.ptr
llvm.store %165, %167 : i64, !llvm.ptr
%168 = llvm.load %133 : !llvm.ptr -> i64
%169 = arith.constant 4 : i32
%171 = arith.extsi %169 : i32 to i64
%170 = arith.divsi %141, %171 : i64
%172 = arith.cmpi sgt, %168, %170 : i64
cf.cond_br %172, ^bb18, ^bb19
^bb18:
%173 = arith.constant 4 : i32
%175 = arith.extsi %173 : i32 to i64
%174 = arith.divsi %141, %175 : i64
llvm.store %174, %167 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%176 = llvm.load %133 : !llvm.ptr -> i64
%177 = arith.constant 2 : i32
%179 = arith.extsi %177 : i32 to i64
%178 = arith.remsi %176, %179 : i64
%180 = arith.constant 0 : i32
%181 = arith.extsi %180 : i32 to i64
%182 = llvm.mlir.constant(1 : i64) : i64
%183 = llvm.alloca %182 x i64 : (i64) -> !llvm.ptr
llvm.store %181, %183 : i64, !llvm.ptr
%185 = llvm.load %133 : !llvm.ptr -> i64
%186 = llvm.getelementptr %41[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%184 = llvm.load %186 : !llvm.ptr -> i64
%188 = llvm.getelementptr %41[%141] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%187 = llvm.load %188 : !llvm.ptr -> i64
%189 = llvm.mlir.constant(1 : i64) : i64
%190 = llvm.alloca %189 x i64 : (i64) -> !llvm.ptr
llvm.store %178, %190 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%191 = llvm.load %190 : !llvm.ptr -> i64
%192 = llvm.load %167 : !llvm.ptr -> i64
%193 = arith.cmpi sle, %191, %192 : i64
cf.cond_br %193, ^bb22, ^bb23
^bb22:
%194 = llvm.load %133 : !llvm.ptr -> i64
%195 = llvm.load %190 : !llvm.ptr -> i64
%196 = arith.addi %194, %195 : i64
%197 = arith.constant 2 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.divsi %196, %199 : i64
%200 = arith.constant 4 : i32
%201 = llvm.load %190 : !llvm.ptr -> i64
%203 = arith.extsi %200 : i32 to i64
%202 = arith.muli %203, %201 : i64
%204 = arith.subi %141, %202 : i64
%205 = arith.constant 2 : i32
%207 = arith.extsi %205 : i32 to i64
%206 = arith.divsi %204, %207 : i64
%209 = llvm.getelementptr %50[%198] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%208 = llvm.load %209 : !llvm.ptr -> i64
%210 = arith.muli %184, %208 : i64
%211 = llvm.mlir.addressof @MOD : !llvm.ptr
%212 = llvm.load %211 : !llvm.ptr -> i64
%213 = arith.remsi %210, %212 : i64
%215 = llvm.load %133 : !llvm.ptr -> i64
%216 = arith.subi %215, %198 : i64
%217 = llvm.getelementptr %50[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%214 = llvm.load %217 : !llvm.ptr -> i64
%218 = arith.muli %213, %214 : i64
%219 = llvm.mlir.addressof @MOD : !llvm.ptr
%220 = llvm.load %219 : !llvm.ptr -> i64
%221 = arith.remsi %218, %220 : i64
%223 = llvm.getelementptr %50[%206] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%222 = llvm.load %223 : !llvm.ptr -> i64
%224 = arith.muli %187, %222 : i64
%225 = llvm.mlir.addressof @MOD : !llvm.ptr
%226 = llvm.load %225 : !llvm.ptr -> i64
%227 = arith.remsi %224, %226 : i64
%229 = arith.subi %141, %206 : i64
%230 = llvm.getelementptr %50[%229] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%228 = llvm.load %230 : !llvm.ptr -> i64
%231 = arith.muli %227, %228 : i64
%232 = llvm.mlir.addressof @MOD : !llvm.ptr
%233 = llvm.load %232 : !llvm.ptr -> i64
%234 = arith.remsi %231, %233 : i64
%235 = arith.muli %221, %234 : i64
%236 = llvm.mlir.addressof @MOD : !llvm.ptr
%237 = llvm.load %236 : !llvm.ptr -> i64
%238 = arith.remsi %235, %237 : i64
%239 = llvm.load %190 : !llvm.ptr -> i64
%240 = arith.constant 0 : i32
%242 = arith.extsi %240 : i32 to i64
%241 = arith.cmpi eq, %239, %242 : i64
cf.cond_br %241, ^bb24, ^bb25
^bb24:
%243 = llvm.load %183 : !llvm.ptr -> i64
%244 = arith.addi %243, %238 : i64
llvm.store %244, %183 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
%245 = llvm.load %183 : !llvm.ptr -> i64
%246 = arith.constant 2 : i32
%248 = arith.extsi %246 : i32 to i64
%247 = arith.muli %238, %248 : i64
%249 = arith.addi %245, %247 : i64
llvm.store %249, %183 : i64, !llvm.ptr
cf.br ^bb26
^bb26:
%250 = llvm.load %190 : !llvm.ptr -> i64
%251 = arith.constant 2 : i32
%253 = arith.extsi %251 : i32 to i64
%252 = arith.addi %250, %253 : i64
llvm.store %252, %190 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%254 = llvm.load %129 : !llvm.ptr -> i64
%255 = llvm.load %183 : !llvm.ptr -> i64
%256 = llvm.mlir.addressof @MOD : !llvm.ptr
%257 = llvm.load %256 : !llvm.ptr -> i64
%258 = arith.remsi %255, %257 : i64
%259 = arith.muli %164, %258 : i64
%260 = arith.addi %254, %259 : i64
%261 = llvm.mlir.addressof @MOD : !llvm.ptr
%262 = llvm.load %261 : !llvm.ptr -> i64
%263 = arith.remsi %260, %262 : i64
llvm.store %263, %129 : i64, !llvm.ptr
%264 = llvm.load %133 : !llvm.ptr -> i64
%265 = arith.constant 1 : i32
%267 = arith.extsi %265 : i32 to i64
%266 = arith.addi %264, %267 : i64
llvm.store %266, %133 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%268 = llvm.mlir.addressof @str_0 : !llvm.ptr
%269 = llvm.load %129 : !llvm.ptr -> i64
%270 = llvm.call @printf(%268, %269) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%41) : (!llvm.ptr) -> ()
func.call @free(%50) : (!llvm.ptr) -> ()
%273 = arith.constant 0 : i32
func.return %273 : i32
}
}