← All problems Problem 414
Sum of S(6k+3) for k=2..300, mod 10^18 (Kaprekar base-b 5-digit).
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^2)O(n)Approach Flow solution Sieve or enumeration Verdict Suboptimal
Flow source
# Project Euler 414
# Sum of S(6k+3) for k=2..300, mod 10^18 (Kaprekar base-b 5-digit).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function idx(p: i64, q: i64) -> i64 {
return p * (p + 1) / 2 + q
}
function S_base(b: i64) -> i64 {
let MOD: i64 = 1000000000000000000
let t: i64 = (b - 3) / 6
let p_star: i64 = 4 * t + 2
let q_star: i64 = 2 * t + 1
let size: i64 = b * (b + 1) / 2
let target: i64 = idx(p_star, q_star)
let nxt: ptr<i32> = calloc(size, 4)
let w: ptr<i64> = calloc(size, 8)
let dist: ptr<i16> = calloc(size, 2)
if nxt == null || w == null || dist == null { return -1 }
let mut p: i64 = 1
while p < b {
let base: i64 = p * (p + 1) / 2
let bp: i64 = b - p
# q = 0
let c: i64 = p - 1
let a: i64 = bp
let mut mn: i64 = a
let mut mx: i64 = c
if c < a { mn = c; mx = a }
let p2: i64 = b - 1 - mn
let q2: i64 = b - 1 - mx
nxt[base + 0] = idx(p2, q2) as i32
w[base + 0] = bp * (20 * p - 10)
let mut q: i64 = 1
while q <= p {
let mut a1: i64 = p
let mut a2: i64 = bp
let mut a3: i64 = q - 1
let mut a4: i64 = b - q - 1
if a1 > a2 { let tmp: i64 = a1; a1 = a2; a2 = tmp }
if a3 > a4 { let tmp2: i64 = a3; a3 = a4; a4 = tmp2 }
if a1 > a3 { let tmp3: i64 = a1; a1 = a3; a3 = tmp3 }
if a2 > a4 { let tmp4: i64 = a2; a2 = a4; a4 = tmp4 }
if a2 > a3 { let tmp5: i64 = a2; a2 = a3; a3 = tmp5 }
let p2b: i64 = b - 1 - a1
let q2b: i64 = a4 - a2
nxt[base + q] = idx(p2b, q2b) as i32
if q < p {
w[base + q] = bp * (120 * q * (p - q) - 20)
} else {
w[base + q] = bp * (30 * p - 10)
}
q = q + 1
}
p = p + 1
}
let mut i: i64 = 0
while i < size {
dist[i] = -1
i = i + 1
}
dist[0] = 0
dist[target] = 0
let path: ptr<i32> = calloc(size, 4)
if path == null { return -1 }
let mut total: i64 = 0
i = 1
while i < size {
if dist[i] == -1 {
let mut cur: i64 = i
let mut plen: i64 = 0
while dist[cur] == -1 {
path[plen] = cur as i32
plen = plen + 1
cur = nxt[cur] as i64
}
let mut d: i64 = dist[cur] as i64
let mut k: i64 = plen - 1
while k >= 0 {
d = d + 1
let node: i64 = path[k] as i64
dist[node] = d as i16
total = (total + w[node] * (d + 1)) % MOD
k = k - 1
}
}
i = i + 1
}
free(path)
total = (total + w[target] * 1) % MOD
total = total - 1
if total < 0 { total = total + MOD }
free(dist)
free(w)
free(nxt)
return total
}
function main() -> i32 {
let MOD: i64 = 1000000000000000000
let mut total: i64 = 0
let mut k: i64 = 2
while k <= 300 {
let b: i64 = 6 * k + 3
total = (total + S_base(b)) % MOD
k = k + 1
}
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; }
int64_t idx_i64_i64(int64_t p, int64_t q);
int64_t S_base_i64(int64_t b);
int32_t main(void);
int64_t idx_i64_i64(int64_t p, int64_t q) {
return (FLOW_CHECKED_DIV(((p * (p + 1))), (2)) + q);
}
int64_t S_base_i64(int64_t b) {
int64_t MOD = 1000000000000000000;
int64_t t = FLOW_CHECKED_DIV(((b - 3)), (6));
int64_t p_star = ((4 * t) + 2);
int64_t q_star = ((2 * t) + 1);
int64_t size = FLOW_CHECKED_DIV(((b * (b + 1))), (2));
int64_t target = idx_i64_i64(p_star, q_star);
int32_t* nxt = (int32_t*)(calloc(size, 4));
int64_t* w = (int64_t*)(calloc(size, 8));
int16_t* dist = (int16_t*)(calloc(size, 2));
if (((nxt == NULL || w == NULL) || dist == NULL)) {
return (-1);
}
int64_t p = 1;
while (p < b) {
int64_t base = FLOW_CHECKED_DIV(((p * (p + 1))), (2));
int64_t bp = (b - p);
int64_t c = (p - 1);
int64_t a = bp;
int64_t mn = a;
int64_t mx = c;
if (c < a) {
mn = c;
mx = a;
}
int64_t p2 = ((b - 1) - mn);
int64_t q2 = ((b - 1) - mx);
nxt[(base + 0)] = ((int32_t)(idx_i64_i64(p2, q2)));
w[(base + 0)] = (bp * ((20 * p) - 10));
int64_t q = 1;
while (q <= p) {
int64_t a1 = p;
int64_t a2 = bp;
int64_t a3 = (q - 1);
int64_t a4 = ((b - q) - 1);
if (a1 > a2) {
int64_t tmp = a1;
a1 = a2;
a2 = tmp;
}
if (a3 > a4) {
int64_t tmp2 = a3;
a3 = a4;
a4 = tmp2;
}
if (a1 > a3) {
int64_t tmp3 = a1;
a1 = a3;
a3 = tmp3;
}
if (a2 > a4) {
int64_t tmp4 = a2;
a2 = a4;
a4 = tmp4;
}
if (a2 > a3) {
int64_t tmp5 = a2;
a2 = a3;
a3 = tmp5;
}
int64_t p2b = ((b - 1) - a1);
int64_t q2b = (a4 - a2);
nxt[(base + q)] = ((int32_t)(idx_i64_i64(p2b, q2b)));
if (q < p) {
w[(base + q)] = (bp * (((120 * q) * (p - q)) - 20));
} else {
w[(base + q)] = (bp * ((30 * p) - 10));
}
q = (q + 1);
}
p = (p + 1);
}
int64_t i = 0;
while (i < size) {
dist[i] = (-1);
i = (i + 1);
}
dist[0] = 0;
dist[target] = 0;
int32_t* path = (int32_t*)(calloc(size, 4));
if (path == NULL) {
return (-1);
}
int64_t total = 0;
i = 1;
while (i < size) {
if (dist[i] == (-1)) {
int64_t cur = i;
int64_t plen = 0;
while (dist[cur] == (-1)) {
path[plen] = ((int32_t)(cur));
plen = (plen + 1);
cur = ((int64_t)(nxt[cur]));
}
int64_t d = ((int64_t)(dist[cur]));
int64_t k = (plen - 1);
while (k >= 0) {
d = (d + 1);
int64_t node = ((int64_t)(path[k]));
dist[node] = ((int16_t)(d));
total = FLOW_CHECKED_MOD(((total + (w[node] * (d + 1)))), (MOD));
k = (k - 1);
}
}
i = (i + 1);
}
free(path);
total = FLOW_CHECKED_MOD(((total + (w[target] * 1))), (MOD));
total = (total - 1);
if (total < 0) {
total = (total + MOD);
}
free(dist);
free(w);
free(nxt);
return total;
}
int32_t main(void) {
int64_t MOD = 1000000000000000000;
int64_t total = 0;
int64_t k = 2;
while (k <= 300) {
int64_t b = ((6 * k) + 3);
total = FLOW_CHECKED_MOD(((total + S_base_i64(b))), (MOD));
k = (k + 1);
}
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 @idx(%arg0: i64, %arg1: i64) -> i64 {
%0 = arith.constant 1 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.addi %arg0, %2 : i64
%3 = arith.muli %arg0, %1 : i64
%4 = arith.constant 2 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.divsi %3, %6 : i64
%7 = arith.addi %5, %arg1 : i64
func.return %7 : i64
}
func.func @S_base(%arg0: i64) -> i64 {
%8 = arith.constant 999999995705032704 : i32
%9 = arith.extsi %8 : i32 to i64
%10 = arith.constant 3 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.subi %arg0, %12 : i64
%13 = arith.constant 6 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.divsi %11, %15 : i64
%16 = arith.constant 4 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.muli %18, %14 : i64
%19 = arith.constant 2 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.addi %17, %21 : i64
%22 = arith.constant 2 : i32
%24 = arith.extsi %22 : i32 to i64
%23 = arith.muli %24, %14 : i64
%25 = arith.constant 1 : i32
%27 = arith.extsi %25 : i32 to i64
%26 = arith.addi %23, %27 : i64
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.addi %arg0, %30 : i64
%31 = arith.muli %arg0, %29 : i64
%32 = arith.constant 2 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.divsi %31, %34 : i64
%35 = func.call @idx(%20, %26) : (i64, i64) -> i64
%37 = arith.constant 4 : i32
%38 = arith.extsi %37 : i32 to i64
%36 = func.call @calloc(%33, %38) : (i64, i64) -> !llvm.ptr
%40 = arith.constant 8 : i32
%41 = arith.extsi %40 : i32 to i64
%39 = func.call @calloc(%33, %41) : (i64, i64) -> !llvm.ptr
%43 = arith.constant 2 : i32
%44 = arith.extsi %43 : i32 to i64
%42 = func.call @calloc(%33, %44) : (i64, i64) -> !llvm.ptr
%45 = llvm.mlir.zero : !llvm.ptr
%46 = llvm.icmp "eq" %36, %45 : !llvm.ptr
%47 = scf.if %46 -> (i1) {
%48 = arith.constant true
scf.yield %48 : i1
} else {
%49 = llvm.mlir.zero : !llvm.ptr
%50 = llvm.icmp "eq" %39, %49 : !llvm.ptr
scf.yield %50 : i1
}
%51 = scf.if %47 -> (i1) {
%52 = arith.constant true
scf.yield %52 : i1
} else {
%53 = llvm.mlir.zero : !llvm.ptr
%54 = llvm.icmp "eq" %42, %53 : !llvm.ptr
scf.yield %54 : i1
}
cf.cond_br %51, ^bb0, ^bb1
^bb0:
%55 = arith.constant 1 : i32
%57 = arith.constant 0 : i32
%56 = arith.subi %57, %55 : i32
%58 = arith.extsi %56 : i32 to i64
func.return %58 : i64
^bb1:
cf.br ^bb2
^bb2:
%59 = arith.constant 1 : i32
%60 = arith.extsi %59 : i32 to i64
%61 = llvm.mlir.constant(1 : i64) : i64
%62 = llvm.alloca %61 x i64 : (i64) -> !llvm.ptr
llvm.store %60, %62 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%63 = llvm.load %62 : !llvm.ptr -> i64
%64 = arith.cmpi slt, %63, %arg0 : i64
cf.cond_br %64, ^bb4, ^bb5
^bb4:
%65 = llvm.load %62 : !llvm.ptr -> i64
%66 = llvm.load %62 : !llvm.ptr -> i64
%67 = arith.constant 1 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.addi %66, %69 : i64
%70 = arith.muli %65, %68 : i64
%71 = arith.constant 2 : i32
%73 = arith.extsi %71 : i32 to i64
%72 = arith.divsi %70, %73 : i64
%74 = llvm.load %62 : !llvm.ptr -> i64
%75 = arith.subi %arg0, %74 : i64
%76 = llvm.load %62 : !llvm.ptr -> i64
%77 = arith.constant 1 : i32
%79 = arith.extsi %77 : i32 to i64
%78 = arith.subi %76, %79 : i64
%80 = llvm.mlir.constant(1 : i64) : i64
%81 = llvm.alloca %80 x i64 : (i64) -> !llvm.ptr
llvm.store %75, %81 : i64, !llvm.ptr
%82 = llvm.mlir.constant(1 : i64) : i64
%83 = llvm.alloca %82 x i64 : (i64) -> !llvm.ptr
llvm.store %78, %83 : i64, !llvm.ptr
%84 = arith.cmpi slt, %78, %75 : i64
cf.cond_br %84, ^bb6, ^bb7
^bb6:
llvm.store %78, %81 : i64, !llvm.ptr
llvm.store %75, %83 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%85 = arith.constant 1 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.subi %arg0, %87 : i64
%88 = llvm.load %81 : !llvm.ptr -> i64
%89 = arith.subi %86, %88 : i64
%90 = arith.constant 1 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.subi %arg0, %92 : i64
%93 = llvm.load %83 : !llvm.ptr -> i64
%94 = arith.subi %91, %93 : i64
%95 = func.call @idx(%89, %94) : (i64, i64) -> i64
%96 = arith.trunci %95 : i64 to i32
%97 = arith.constant 0 : i32
%99 = arith.extsi %97 : i32 to i64
%98 = arith.addi %72, %99 : i64
%100 = llvm.getelementptr %36[%98] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %96, %100 : i32, !llvm.ptr
%101 = arith.constant 20 : i32
%102 = llvm.load %62 : !llvm.ptr -> i64
%104 = arith.extsi %101 : i32 to i64
%103 = arith.muli %104, %102 : i64
%105 = arith.constant 10 : i32
%107 = arith.extsi %105 : i32 to i64
%106 = arith.subi %103, %107 : i64
%108 = arith.muli %75, %106 : i64
%109 = arith.constant 0 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.addi %72, %111 : i64
%112 = llvm.getelementptr %39[%110] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %108, %112 : i64, !llvm.ptr
%113 = arith.constant 1 : i32
%114 = arith.extsi %113 : i32 to i64
%115 = llvm.mlir.constant(1 : i64) : i64
%116 = llvm.alloca %115 x i64 : (i64) -> !llvm.ptr
llvm.store %114, %116 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%117 = llvm.load %116 : !llvm.ptr -> i64
%118 = llvm.load %62 : !llvm.ptr -> i64
%119 = arith.cmpi sle, %117, %118 : i64
cf.cond_br %119, ^bb10, ^bb11
^bb10:
%120 = llvm.load %62 : !llvm.ptr -> i64
%121 = llvm.mlir.constant(1 : i64) : i64
%122 = llvm.alloca %121 x i64 : (i64) -> !llvm.ptr
llvm.store %120, %122 : i64, !llvm.ptr
%123 = llvm.mlir.constant(1 : i64) : i64
%124 = llvm.alloca %123 x i64 : (i64) -> !llvm.ptr
llvm.store %75, %124 : i64, !llvm.ptr
%125 = llvm.load %116 : !llvm.ptr -> i64
%126 = arith.constant 1 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.subi %125, %128 : i64
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i64 : (i64) -> !llvm.ptr
llvm.store %127, %130 : i64, !llvm.ptr
%131 = llvm.load %116 : !llvm.ptr -> i64
%132 = arith.subi %arg0, %131 : i64
%133 = arith.constant 1 : i32
%135 = arith.extsi %133 : i32 to i64
%134 = arith.subi %132, %135 : i64
%136 = llvm.mlir.constant(1 : i64) : i64
%137 = llvm.alloca %136 x i64 : (i64) -> !llvm.ptr
llvm.store %134, %137 : i64, !llvm.ptr
%138 = llvm.load %122 : !llvm.ptr -> i64
%139 = llvm.load %124 : !llvm.ptr -> i64
%140 = arith.cmpi sgt, %138, %139 : i64
cf.cond_br %140, ^bb12, ^bb13
^bb12:
%141 = llvm.load %122 : !llvm.ptr -> i64
%142 = llvm.load %124 : !llvm.ptr -> i64
llvm.store %142, %122 : i64, !llvm.ptr
llvm.store %141, %124 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%143 = llvm.load %130 : !llvm.ptr -> i64
%144 = llvm.load %137 : !llvm.ptr -> i64
%145 = arith.cmpi sgt, %143, %144 : i64
cf.cond_br %145, ^bb15, ^bb16
^bb15:
%146 = llvm.load %130 : !llvm.ptr -> i64
%147 = llvm.load %137 : !llvm.ptr -> i64
llvm.store %147, %130 : i64, !llvm.ptr
llvm.store %146, %137 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%148 = llvm.load %122 : !llvm.ptr -> i64
%149 = llvm.load %130 : !llvm.ptr -> i64
%150 = arith.cmpi sgt, %148, %149 : i64
cf.cond_br %150, ^bb18, ^bb19
^bb18:
%151 = llvm.load %122 : !llvm.ptr -> i64
%152 = llvm.load %130 : !llvm.ptr -> i64
llvm.store %152, %122 : i64, !llvm.ptr
llvm.store %151, %130 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%153 = llvm.load %124 : !llvm.ptr -> i64
%154 = llvm.load %137 : !llvm.ptr -> i64
%155 = arith.cmpi sgt, %153, %154 : i64
cf.cond_br %155, ^bb21, ^bb22
^bb21:
%156 = llvm.load %124 : !llvm.ptr -> i64
%157 = llvm.load %137 : !llvm.ptr -> i64
llvm.store %157, %124 : i64, !llvm.ptr
llvm.store %156, %137 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%158 = llvm.load %124 : !llvm.ptr -> i64
%159 = llvm.load %130 : !llvm.ptr -> i64
%160 = arith.cmpi sgt, %158, %159 : i64
cf.cond_br %160, ^bb24, ^bb25
^bb24:
%161 = llvm.load %124 : !llvm.ptr -> i64
%162 = llvm.load %130 : !llvm.ptr -> i64
llvm.store %162, %124 : i64, !llvm.ptr
llvm.store %161, %130 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%163 = arith.constant 1 : i32
%165 = arith.extsi %163 : i32 to i64
%164 = arith.subi %arg0, %165 : i64
%166 = llvm.load %122 : !llvm.ptr -> i64
%167 = arith.subi %164, %166 : i64
%168 = llvm.load %137 : !llvm.ptr -> i64
%169 = llvm.load %124 : !llvm.ptr -> i64
%170 = arith.subi %168, %169 : i64
%171 = func.call @idx(%167, %170) : (i64, i64) -> i64
%172 = arith.trunci %171 : i64 to i32
%173 = llvm.load %116 : !llvm.ptr -> i64
%174 = arith.addi %72, %173 : i64
%175 = llvm.getelementptr %36[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %172, %175 : i32, !llvm.ptr
%176 = llvm.load %116 : !llvm.ptr -> i64
%177 = llvm.load %62 : !llvm.ptr -> i64
%178 = arith.cmpi slt, %176, %177 : i64
cf.cond_br %178, ^bb27, ^bb28
^bb27:
%179 = arith.constant 120 : i32
%180 = llvm.load %116 : !llvm.ptr -> i64
%182 = arith.extsi %179 : i32 to i64
%181 = arith.muli %182, %180 : i64
%183 = llvm.load %62 : !llvm.ptr -> i64
%184 = llvm.load %116 : !llvm.ptr -> i64
%185 = arith.subi %183, %184 : i64
%186 = arith.muli %181, %185 : i64
%187 = arith.constant 20 : i32
%189 = arith.extsi %187 : i32 to i64
%188 = arith.subi %186, %189 : i64
%190 = arith.muli %75, %188 : i64
%191 = llvm.load %116 : !llvm.ptr -> i64
%192 = arith.addi %72, %191 : i64
%193 = llvm.getelementptr %39[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %190, %193 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
%194 = arith.constant 30 : i32
%195 = llvm.load %62 : !llvm.ptr -> i64
%197 = arith.extsi %194 : i32 to i64
%196 = arith.muli %197, %195 : i64
%198 = arith.constant 10 : i32
%200 = arith.extsi %198 : i32 to i64
%199 = arith.subi %196, %200 : i64
%201 = arith.muli %75, %199 : i64
%202 = llvm.load %116 : !llvm.ptr -> i64
%203 = arith.addi %72, %202 : i64
%204 = llvm.getelementptr %39[%203] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %201, %204 : i64, !llvm.ptr
cf.br ^bb29
^bb29:
%205 = llvm.load %116 : !llvm.ptr -> i64
%206 = arith.constant 1 : i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.addi %205, %208 : i64
llvm.store %207, %116 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%209 = llvm.load %62 : !llvm.ptr -> i64
%210 = arith.constant 1 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.addi %209, %212 : i64
llvm.store %211, %62 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%213 = arith.constant 0 : i32
%214 = arith.extsi %213 : i32 to i64
%215 = llvm.mlir.constant(1 : i64) : i64
%216 = llvm.alloca %215 x i64 : (i64) -> !llvm.ptr
llvm.store %214, %216 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%217 = llvm.load %216 : !llvm.ptr -> i64
%218 = arith.cmpi slt, %217, %33 : i64
cf.cond_br %218, ^bb31, ^bb32
^bb31:
%219 = arith.constant 1 : i32
%221 = arith.constant 0 : i32
%220 = arith.subi %221, %219 : i32
%222 = llvm.load %216 : !llvm.ptr -> i64
%223 = arith.trunci %220 : i32 to i16
%224 = llvm.getelementptr %42[%222] : (!llvm.ptr, i64) -> !llvm.ptr, i16
llvm.store %223, %224 : i16, !llvm.ptr
%225 = llvm.load %216 : !llvm.ptr -> i64
%226 = arith.constant 1 : i32
%228 = arith.extsi %226 : i32 to i64
%227 = arith.addi %225, %228 : i64
llvm.store %227, %216 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%229 = arith.constant 0 : i32
%230 = arith.constant 0 : i32
%231 = arith.trunci %229 : i32 to i16
%232 = arith.extsi %230 : i32 to i64
%233 = llvm.getelementptr %42[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i16
llvm.store %231, %233 : i16, !llvm.ptr
%234 = arith.constant 0 : i32
%235 = arith.trunci %234 : i32 to i16
%236 = llvm.getelementptr %42[%35] : (!llvm.ptr, i64) -> !llvm.ptr, i16
llvm.store %235, %236 : i16, !llvm.ptr
%238 = arith.constant 4 : i32
%239 = arith.extsi %238 : i32 to i64
%237 = func.call @calloc(%33, %239) : (i64, i64) -> !llvm.ptr
%240 = llvm.mlir.zero : !llvm.ptr
%241 = llvm.icmp "eq" %237, %240 : !llvm.ptr
cf.cond_br %241, ^bb33, ^bb34
^bb33:
%242 = arith.constant 1 : i32
%244 = arith.constant 0 : i32
%243 = arith.subi %244, %242 : i32
%245 = arith.extsi %243 : i32 to i64
func.return %245 : i64
^bb34:
cf.br ^bb35
^bb35:
%246 = arith.constant 0 : i32
%247 = arith.extsi %246 : i32 to i64
%248 = llvm.mlir.constant(1 : i64) : i64
%249 = llvm.alloca %248 x i64 : (i64) -> !llvm.ptr
llvm.store %247, %249 : i64, !llvm.ptr
%250 = arith.constant 1 : i32
%251 = arith.extsi %250 : i32 to i64
llvm.store %251, %216 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%252 = llvm.load %216 : !llvm.ptr -> i64
%253 = arith.cmpi slt, %252, %33 : i64
cf.cond_br %253, ^bb37, ^bb38
^bb37:
%255 = llvm.load %216 : !llvm.ptr -> i64
%256 = llvm.getelementptr %42[%255] : (!llvm.ptr, i64) -> !llvm.ptr, i16
%254 = llvm.load %256 : !llvm.ptr -> i16
%257 = arith.constant 1 : i32
%259 = arith.constant 0 : i32
%258 = arith.subi %259, %257 : i32
%261 = arith.extsi %254 : i16 to i32
%260 = arith.cmpi eq, %261, %258 : i32
cf.cond_br %260, ^bb39, ^bb40
^bb39:
%262 = llvm.load %216 : !llvm.ptr -> i64
%263 = llvm.mlir.constant(1 : i64) : i64
%264 = llvm.alloca %263 x i64 : (i64) -> !llvm.ptr
llvm.store %262, %264 : i64, !llvm.ptr
%265 = arith.constant 0 : i32
%266 = arith.extsi %265 : i32 to i64
%267 = llvm.mlir.constant(1 : i64) : i64
%268 = llvm.alloca %267 x i64 : (i64) -> !llvm.ptr
llvm.store %266, %268 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%270 = llvm.load %264 : !llvm.ptr -> i64
%271 = llvm.getelementptr %42[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i16
%269 = llvm.load %271 : !llvm.ptr -> i16
%272 = arith.constant 1 : i32
%274 = arith.constant 0 : i32
%273 = arith.subi %274, %272 : i32
%276 = arith.extsi %269 : i16 to i32
%275 = arith.cmpi eq, %276, %273 : i32
cf.cond_br %275, ^bb43, ^bb44
^bb43:
%277 = llvm.load %264 : !llvm.ptr -> i64
%278 = arith.trunci %277 : i64 to i32
%279 = llvm.load %268 : !llvm.ptr -> i64
%280 = llvm.getelementptr %237[%279] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %278, %280 : i32, !llvm.ptr
%281 = llvm.load %268 : !llvm.ptr -> i64
%282 = arith.constant 1 : i32
%284 = arith.extsi %282 : i32 to i64
%283 = arith.addi %281, %284 : i64
llvm.store %283, %268 : i64, !llvm.ptr
%286 = llvm.load %264 : !llvm.ptr -> i64
%287 = llvm.getelementptr %36[%286] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%285 = llvm.load %287 : !llvm.ptr -> i32
%288 = arith.extsi %285 : i32 to i64
llvm.store %288, %264 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%290 = llvm.load %264 : !llvm.ptr -> i64
%291 = llvm.getelementptr %42[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i16
%289 = llvm.load %291 : !llvm.ptr -> i16
%292 = arith.extsi %289 : i16 to i64
%293 = llvm.mlir.constant(1 : i64) : i64
%294 = llvm.alloca %293 x i64 : (i64) -> !llvm.ptr
llvm.store %292, %294 : i64, !llvm.ptr
%295 = llvm.load %268 : !llvm.ptr -> i64
%296 = arith.constant 1 : i32
%298 = arith.extsi %296 : i32 to i64
%297 = arith.subi %295, %298 : i64
%299 = llvm.mlir.constant(1 : i64) : i64
%300 = llvm.alloca %299 x i64 : (i64) -> !llvm.ptr
llvm.store %297, %300 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%301 = llvm.load %300 : !llvm.ptr -> i64
%302 = arith.constant 0 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.cmpi sge, %301, %304 : i64
cf.cond_br %303, ^bb46, ^bb47
^bb46:
%305 = llvm.load %294 : !llvm.ptr -> i64
%306 = arith.constant 1 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.addi %305, %308 : i64
llvm.store %307, %294 : i64, !llvm.ptr
%310 = llvm.load %300 : !llvm.ptr -> i64
%311 = llvm.getelementptr %237[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%309 = llvm.load %311 : !llvm.ptr -> i32
%312 = arith.extsi %309 : i32 to i64
%313 = llvm.load %294 : !llvm.ptr -> i64
%314 = arith.trunci %313 : i64 to i16
%315 = llvm.getelementptr %42[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i16
llvm.store %314, %315 : i16, !llvm.ptr
%316 = llvm.load %249 : !llvm.ptr -> i64
%318 = llvm.getelementptr %39[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%317 = llvm.load %318 : !llvm.ptr -> i64
%319 = llvm.load %294 : !llvm.ptr -> i64
%320 = arith.constant 1 : i32
%322 = arith.extsi %320 : i32 to i64
%321 = arith.addi %319, %322 : i64
%323 = arith.muli %317, %321 : i64
%324 = arith.addi %316, %323 : i64
%325 = arith.remsi %324, %9 : i64
llvm.store %325, %249 : i64, !llvm.ptr
%326 = llvm.load %300 : !llvm.ptr -> i64
%327 = arith.constant 1 : i32
%329 = arith.extsi %327 : i32 to i64
%328 = arith.subi %326, %329 : i64
llvm.store %328, %300 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%330 = llvm.load %216 : !llvm.ptr -> i64
%331 = arith.constant 1 : i32
%333 = arith.extsi %331 : i32 to i64
%332 = arith.addi %330, %333 : i64
llvm.store %332, %216 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
func.call @free(%237) : (!llvm.ptr) -> ()
%335 = llvm.load %249 : !llvm.ptr -> i64
%337 = llvm.getelementptr %39[%35] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%336 = llvm.load %337 : !llvm.ptr -> i64
%338 = arith.constant 1 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.muli %336, %340 : i64
%341 = arith.addi %335, %339 : i64
%342 = arith.remsi %341, %9 : i64
llvm.store %342, %249 : i64, !llvm.ptr
%343 = llvm.load %249 : !llvm.ptr -> i64
%344 = arith.constant 1 : i32
%346 = arith.extsi %344 : i32 to i64
%345 = arith.subi %343, %346 : i64
llvm.store %345, %249 : i64, !llvm.ptr
%347 = llvm.load %249 : !llvm.ptr -> i64
%348 = arith.constant 0 : i32
%350 = arith.extsi %348 : i32 to i64
%349 = arith.cmpi slt, %347, %350 : i64
cf.cond_br %349, ^bb48, ^bb49
^bb48:
%351 = llvm.load %249 : !llvm.ptr -> i64
%352 = arith.addi %351, %9 : i64
llvm.store %352, %249 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
func.call @free(%42) : (!llvm.ptr) -> ()
func.call @free(%39) : (!llvm.ptr) -> ()
func.call @free(%36) : (!llvm.ptr) -> ()
%356 = llvm.load %249 : !llvm.ptr -> i64
func.return %356 : i64
}
func.func @main() -> i32 {
%357 = arith.constant 999999995705032704 : i32
%358 = arith.extsi %357 : i32 to i64
%359 = arith.constant 0 : i32
%360 = arith.extsi %359 : i32 to i64
%361 = llvm.mlir.constant(1 : i64) : i64
%362 = llvm.alloca %361 x i64 : (i64) -> !llvm.ptr
llvm.store %360, %362 : i64, !llvm.ptr
%363 = arith.constant 2 : i32
%364 = arith.extsi %363 : i32 to i64
%365 = llvm.mlir.constant(1 : i64) : i64
%366 = llvm.alloca %365 x i64 : (i64) -> !llvm.ptr
llvm.store %364, %366 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%367 = llvm.load %366 : !llvm.ptr -> i64
%368 = arith.constant 300 : i32
%370 = arith.extsi %368 : i32 to i64
%369 = arith.cmpi sle, %367, %370 : i64
cf.cond_br %369, ^bb52, ^bb53
^bb52:
%371 = arith.constant 6 : i32
%372 = llvm.load %366 : !llvm.ptr -> i64
%374 = arith.extsi %371 : i32 to i64
%373 = arith.muli %374, %372 : i64
%375 = arith.constant 3 : i32
%377 = arith.extsi %375 : i32 to i64
%376 = arith.addi %373, %377 : i64
%378 = llvm.load %362 : !llvm.ptr -> i64
%379 = func.call @S_base(%376) : (i64) -> i64
%380 = arith.addi %378, %379 : i64
%381 = arith.remsi %380, %358 : i64
llvm.store %381, %362 : i64, !llvm.ptr
%382 = llvm.load %366 : !llvm.ptr -> i64
%383 = arith.constant 1 : i32
%385 = arith.extsi %383 : i32 to i64
%384 = arith.addi %382, %385 : i64
llvm.store %384, %366 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%386 = llvm.mlir.addressof @str_0 : !llvm.ptr
%387 = llvm.load %362 : !llvm.ptr -> i64
%388 = llvm.call @printf(%386, %387) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%389 = arith.constant 0 : i32
func.return %389 : i32
}
}