Problem 477
Number Sequence Game Optimal end-take score for s_0=0, s_{k+1}=(s_k^2+45) mod 10^9+7, N=10^8.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n log n) |
|---|
| Space complexity | O(n) | O(n) |
|---|
| Approach | Flow solution | Modular DP or matrix exponentiation |
|---|
| Verdict | Suboptimal |
|---|
Flow source
# Project Euler 477
# Number Sequence Game
# Optimal end-take score for s_0=0, s_{k+1}=(s_k^2+45) mod 10^9+7, N=10^8.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const N: i64 = 100000000
const PERIOD_MULT: i64 = 8
function next_s(x: i64) -> i64 {
return ((x * x) % MOD + 45) % MOD
}
let mut MU: i64 = 0
let mut LAM: i64 = 0
function floyd() -> void {
let mut tort: i64 = next_s(0)
let mut hare: i64 = next_s(next_s(0))
while tort != hare {
tort = next_s(tort)
hare = next_s(next_s(hare))
}
MU = 0
tort = 0
while tort != hare {
tort = next_s(tort)
hare = next_s(hare)
MU = MU + 1
}
LAM = 1
hare = next_s(tort)
while tort != hare {
hare = next_s(hare)
LAM = LAM + 1
}
}
function value_at(idx1: i64, pref: ptr<i64>, mu: i64, lam: i64) -> i64 {
let k: i64 = idx1 - 1
if k < mu + lam {
return pref[k]
}
return pref[mu + (k - mu) % lam]
}
function optimal_first_sum(seq: ptr<i64>, n: i64) -> i64 {
let dp: ptr<i64> = calloc(n, 8)
if dp == null { return -1 }
let mut i: i64 = n - 1
while i >= 0 {
dp[i] = seq[i]
let mut s: i64 = seq[i]
let mut j: i64 = i + 1
while j < n {
s = s + seq[j]
let x: i64 = dp[j]
let y: i64 = dp[j - 1]
let mut m: i64 = x
if y < m { m = y }
dp[j] = s - m
j = j + 1
}
i = i - 1
}
let ans: i64 = dp[n - 1]
free(dp)
return ans
}
function main() -> i32 {
floyd()
let period: i64 = PERIOD_MULT * LAM
let m: i64 = MU + LAM
let pref: ptr<i64> = calloc(m, 8)
if pref == null { return 1 }
pref[0] = 0
let mut x: i64 = 0
let mut t: i64 = 1
while t < m {
x = next_s(x)
pref[t] = x
t = t + 1
}
let mut lx: i64 = N
let mut kblocks: i64 = 0
while lx > period {
let v1: i64 = value_at(lx, pref, MU, LAM)
let v2: i64 = value_at(lx - period, pref, MU, LAM)
if v1 != v2 { break }
lx = lx - period
kblocks = kblocks + 1
}
# Build the reduced sequence and DP its optimal first-player sum.
let seq: ptr<i64> = calloc(lx, 8)
if seq == null { return 1 }
let mut i: i64 = 0
while i < lx {
seq[i] = value_at(i + 1, pref, MU, LAM)
i = i + 1
}
let base: i64 = optimal_first_sum(seq, lx)
free(seq)
# DIFF = sum of values on one parity inside one PERIOD block after lx.
let parity: i64 = (lx + 1) & 1
let mut diff: i64 = 0
let start: i64 = lx + 1
let end: i64 = lx + period
let mut idx: i64 = start
while idx <= end {
if (idx & 1) == parity {
diff = diff + value_at(idx, pref, MU, LAM)
}
idx = idx + 1
}
let ans: i64 = base + kblocks * diff
printf("%lld\n", ans)
free(pref)
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 next_s_i64(int64_t x);
void floyd(void);
int64_t value_at_i64_ptr_i64_i64_i64(int64_t idx1, int64_t* pref, int64_t mu, int64_t lam);
int64_t optimal_first_sum_ptr_i64_i64(int64_t* seq, int64_t n);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int64_t N = 100000000;
static const int64_t PERIOD_MULT = 8;
/* Module statics */
static int64_t MU = 0;
static int64_t LAM = 0;
int64_t next_s_i64(int64_t x) {
return FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((x * x)), (MOD)) + 45)), (MOD));
}
void floyd(void) {
int64_t tort = next_s_i64(0);
int64_t hare = next_s_i64(next_s_i64(0));
while (tort != hare) {
tort = next_s_i64(tort);
hare = next_s_i64(next_s_i64(hare));
}
MU = 0;
tort = 0;
while (tort != hare) {
tort = next_s_i64(tort);
hare = next_s_i64(hare);
MU = (MU + 1);
}
LAM = 1;
hare = next_s_i64(tort);
while (tort != hare) {
hare = next_s_i64(hare);
LAM = (LAM + 1);
}
}
int64_t value_at_i64_ptr_i64_i64_i64(int64_t idx1, int64_t* pref, int64_t mu, int64_t lam) {
int64_t k = (idx1 - 1);
if (k < (mu + lam)) {
return pref[k];
}
return pref[(mu + FLOW_CHECKED_MOD(((k - mu)), (lam)))];
}
int64_t optimal_first_sum_ptr_i64_i64(int64_t* seq, int64_t n) {
int64_t* dp = (int64_t*)(calloc(n, 8));
if (dp == NULL) {
return (-1);
}
int64_t i = (n - 1);
while (i >= 0) {
dp[i] = seq[i];
int64_t s = seq[i];
int64_t j = (i + 1);
while (j < n) {
s = (s + seq[j]);
int64_t x = dp[j];
int64_t y = dp[(j - 1)];
int64_t m = x;
if (y < m) {
m = y;
}
dp[j] = (s - m);
j = (j + 1);
}
i = (i - 1);
}
int64_t ans = dp[(n - 1)];
free(dp);
return ans;
}
int32_t main(void) {
floyd();
int64_t period = (PERIOD_MULT * LAM);
int64_t m = (MU + LAM);
int64_t* pref = (int64_t*)(calloc(m, 8));
if (pref == NULL) {
return 1;
}
pref[0] = 0;
int64_t x = 0;
int64_t t = 1;
while (t < m) {
x = next_s_i64(x);
pref[t] = x;
t = (t + 1);
}
int64_t lx = N;
int64_t kblocks = 0;
while (lx > period) {
int64_t v1 = value_at_i64_ptr_i64_i64_i64(lx, pref, MU, LAM);
int64_t v2 = value_at_i64_ptr_i64_i64_i64((lx - period), pref, MU, LAM);
if (v1 != v2) {
break;
}
lx = (lx - period);
kblocks = (kblocks + 1);
}
int64_t* seq = (int64_t*)(calloc(lx, 8));
if (seq == NULL) {
return 1;
}
int64_t i = 0;
while (i < lx) {
seq[i] = value_at_i64_ptr_i64_i64_i64((i + 1), pref, MU, LAM);
i = (i + 1);
}
int64_t base = optimal_first_sum_ptr_i64_i64(seq, lx);
free(seq);
int64_t parity = ((lx + 1) & 1);
int64_t diff = 0;
int64_t start = (lx + 1);
int64_t end = (lx + period);
int64_t idx = start;
while (idx <= end) {
if ((idx & 1) == parity) {
diff = (diff + value_at_i64_ptr_i64_i64_i64(idx, pref, MU, LAM));
}
idx = (idx + 1);
}
int64_t ans = (base + (kblocks * diff));
printf("%lld\n", ans);
free(pref);
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) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(100000000 : i64) : i64
// Constant: PERIOD_MULT
llvm.mlir.global internal constant @PERIOD_MULT(8 : i64) : i64
func.func @next_s(%arg0: i64) -> i64 {
%0 = arith.muli %arg0, %arg0 : i64
%1 = llvm.mlir.addressof @MOD : !llvm.ptr
%2 = llvm.load %1 : !llvm.ptr -> i64
%3 = arith.remsi %0, %2 : i64
%4 = arith.constant 45 : i32
%6 = arith.extsi %4 : i32 to i64
%5 = arith.addi %3, %6 : i64
%7 = llvm.mlir.addressof @MOD : !llvm.ptr
%8 = llvm.load %7 : !llvm.ptr -> i64
%9 = arith.remsi %5, %8 : i64
func.return %9 : i64
}
// Module static: MU
llvm.mlir.global internal @MU(0 : i64) : i64
// Module static: LAM
llvm.mlir.global internal @LAM(0 : i64) : i64
func.func @floyd() -> () {
%11 = arith.constant 0 : i32
%12 = arith.extsi %11 : i32 to i64
%10 = func.call @next_s(%12) : (i64) -> i64
%13 = llvm.mlir.constant(1 : i64) : i64
%14 = llvm.alloca %13 x i64 : (i64) -> !llvm.ptr
llvm.store %10, %14 : i64, !llvm.ptr
%17 = arith.constant 0 : i32
%18 = arith.extsi %17 : i32 to i64
%16 = func.call @next_s(%18) : (i64) -> i64
%15 = func.call @next_s(%16) : (i64) -> i64
%19 = llvm.mlir.constant(1 : i64) : i64
%20 = llvm.alloca %19 x i64 : (i64) -> !llvm.ptr
llvm.store %15, %20 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%21 = llvm.load %14 : !llvm.ptr -> i64
%22 = llvm.load %20 : !llvm.ptr -> i64
%23 = arith.cmpi ne, %21, %22 : i64
cf.cond_br %23, ^bb1, ^bb2
^bb1:
%25 = llvm.load %14 : !llvm.ptr -> i64
%24 = func.call @next_s(%25) : (i64) -> i64
llvm.store %24, %14 : i64, !llvm.ptr
%28 = llvm.load %20 : !llvm.ptr -> i64
%27 = func.call @next_s(%28) : (i64) -> i64
%26 = func.call @next_s(%27) : (i64) -> i64
llvm.store %26, %20 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%29 = arith.constant 0 : i32
%30 = arith.extsi %29 : i32 to i64
%31 = llvm.mlir.addressof @MU : !llvm.ptr
llvm.store %30, %31 : i64, !llvm.ptr
%32 = arith.constant 0 : i32
%33 = arith.extsi %32 : i32 to i64
llvm.store %33, %14 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%34 = llvm.load %14 : !llvm.ptr -> i64
%35 = llvm.load %20 : !llvm.ptr -> i64
%36 = arith.cmpi ne, %34, %35 : i64
cf.cond_br %36, ^bb4, ^bb5
^bb4:
%38 = llvm.load %14 : !llvm.ptr -> i64
%37 = func.call @next_s(%38) : (i64) -> i64
llvm.store %37, %14 : i64, !llvm.ptr
%40 = llvm.load %20 : !llvm.ptr -> i64
%39 = func.call @next_s(%40) : (i64) -> i64
llvm.store %39, %20 : i64, !llvm.ptr
%41 = llvm.mlir.addressof @MU : !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> i64
%43 = arith.constant 1 : i32
%45 = arith.extsi %43 : i32 to i64
%44 = arith.addi %42, %45 : i64
%46 = llvm.mlir.addressof @MU : !llvm.ptr
llvm.store %44, %46 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%47 = arith.constant 1 : i32
%48 = arith.extsi %47 : i32 to i64
%49 = llvm.mlir.addressof @LAM : !llvm.ptr
llvm.store %48, %49 : i64, !llvm.ptr
%51 = llvm.load %14 : !llvm.ptr -> i64
%50 = func.call @next_s(%51) : (i64) -> i64
llvm.store %50, %20 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%52 = llvm.load %14 : !llvm.ptr -> i64
%53 = llvm.load %20 : !llvm.ptr -> i64
%54 = arith.cmpi ne, %52, %53 : i64
cf.cond_br %54, ^bb7, ^bb8
^bb7:
%56 = llvm.load %20 : !llvm.ptr -> i64
%55 = func.call @next_s(%56) : (i64) -> i64
llvm.store %55, %20 : i64, !llvm.ptr
%57 = llvm.mlir.addressof @LAM : !llvm.ptr
%58 = llvm.load %57 : !llvm.ptr -> i64
%59 = arith.constant 1 : i32
%61 = arith.extsi %59 : i32 to i64
%60 = arith.addi %58, %61 : i64
%62 = llvm.mlir.addressof @LAM : !llvm.ptr
llvm.store %60, %62 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
func.return
}
func.func @value_at(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64, %arg3: i64) -> i64 {
%63 = arith.constant 1 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.subi %arg0, %65 : i64
%66 = arith.addi %arg2, %arg3 : i64
%67 = arith.cmpi slt, %64, %66 : i64
cf.cond_br %67, ^bb9, ^bb10
^bb9:
%69 = llvm.getelementptr %arg1[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%68 = llvm.load %69 : !llvm.ptr -> i64
func.return %68 : i64
^bb10:
cf.br ^bb11
^bb11:
%71 = arith.subi %64, %arg2 : i64
%72 = arith.remsi %71, %arg3 : i64
%73 = arith.addi %arg2, %72 : i64
%74 = llvm.getelementptr %arg1[%73] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%70 = llvm.load %74 : !llvm.ptr -> i64
func.return %70 : i64
}
func.func @optimal_first_sum(%arg0: !llvm.ptr, %arg1: i64) -> i64 {
%76 = arith.constant 8 : i32
%77 = arith.extsi %76 : i32 to i64
%75 = func.call @calloc(%arg1, %77) : (i64, i64) -> !llvm.ptr
%78 = llvm.mlir.zero : !llvm.ptr
%79 = llvm.icmp "eq" %75, %78 : !llvm.ptr
cf.cond_br %79, ^bb12, ^bb13
^bb12:
%80 = arith.constant 1 : i32
%82 = arith.constant 0 : i32
%81 = arith.subi %82, %80 : i32
%83 = arith.extsi %81 : i32 to i64
func.return %83 : i64
^bb13:
cf.br ^bb14
^bb14:
%84 = arith.constant 1 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.subi %arg1, %86 : i64
%87 = llvm.mlir.constant(1 : i64) : i64
%88 = llvm.alloca %87 x i64 : (i64) -> !llvm.ptr
llvm.store %85, %88 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%89 = llvm.load %88 : !llvm.ptr -> i64
%90 = arith.constant 0 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.cmpi sge, %89, %92 : i64
cf.cond_br %91, ^bb16, ^bb17
^bb16:
%94 = llvm.load %88 : !llvm.ptr -> i64
%95 = llvm.getelementptr %arg0[%94] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%93 = llvm.load %95 : !llvm.ptr -> i64
%96 = llvm.load %88 : !llvm.ptr -> i64
%97 = llvm.getelementptr %75[%96] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %93, %97 : i64, !llvm.ptr
%99 = llvm.load %88 : !llvm.ptr -> i64
%100 = llvm.getelementptr %arg0[%99] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%98 = llvm.load %100 : !llvm.ptr -> i64
%101 = llvm.mlir.constant(1 : i64) : i64
%102 = llvm.alloca %101 x i64 : (i64) -> !llvm.ptr
llvm.store %98, %102 : i64, !llvm.ptr
%103 = llvm.load %88 : !llvm.ptr -> i64
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.addi %103, %106 : i64
%107 = llvm.mlir.constant(1 : i64) : i64
%108 = llvm.alloca %107 x i64 : (i64) -> !llvm.ptr
llvm.store %105, %108 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%109 = llvm.load %108 : !llvm.ptr -> i64
%110 = arith.cmpi slt, %109, %arg1 : i64
cf.cond_br %110, ^bb19, ^bb20
^bb19:
%111 = llvm.load %102 : !llvm.ptr -> i64
%113 = llvm.load %108 : !llvm.ptr -> i64
%114 = llvm.getelementptr %arg0[%113] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%112 = llvm.load %114 : !llvm.ptr -> i64
%115 = arith.addi %111, %112 : i64
llvm.store %115, %102 : i64, !llvm.ptr
%117 = llvm.load %108 : !llvm.ptr -> i64
%118 = llvm.getelementptr %75[%117] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%116 = llvm.load %118 : !llvm.ptr -> i64
%120 = llvm.load %108 : !llvm.ptr -> i64
%121 = arith.constant 1 : i32
%123 = arith.extsi %121 : i32 to i64
%122 = arith.subi %120, %123 : i64
%124 = llvm.getelementptr %75[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%119 = llvm.load %124 : !llvm.ptr -> i64
%125 = llvm.mlir.constant(1 : i64) : i64
%126 = llvm.alloca %125 x i64 : (i64) -> !llvm.ptr
llvm.store %116, %126 : i64, !llvm.ptr
%127 = llvm.load %126 : !llvm.ptr -> i64
%128 = arith.cmpi slt, %119, %127 : i64
cf.cond_br %128, ^bb21, ^bb22
^bb21:
llvm.store %119, %126 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%129 = llvm.load %102 : !llvm.ptr -> i64
%130 = llvm.load %126 : !llvm.ptr -> i64
%131 = arith.subi %129, %130 : i64
%132 = llvm.load %108 : !llvm.ptr -> i64
%133 = llvm.getelementptr %75[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %131, %133 : i64, !llvm.ptr
%134 = llvm.load %108 : !llvm.ptr -> i64
%135 = arith.constant 1 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.addi %134, %137 : i64
llvm.store %136, %108 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%138 = llvm.load %88 : !llvm.ptr -> i64
%139 = arith.constant 1 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.subi %138, %141 : i64
llvm.store %140, %88 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%143 = arith.constant 1 : i32
%145 = arith.extsi %143 : i32 to i64
%144 = arith.subi %arg1, %145 : i64
%146 = llvm.getelementptr %75[%144] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%142 = llvm.load %146 : !llvm.ptr -> i64
func.call @free(%75) : (!llvm.ptr) -> ()
func.return %142 : i64
}
func.func @main() -> i32 {
func.call @floyd() : () -> ()
%149 = llvm.mlir.addressof @PERIOD_MULT : !llvm.ptr
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.mlir.addressof @LAM : !llvm.ptr
%152 = llvm.load %151 : !llvm.ptr -> i64
%153 = arith.muli %150, %152 : i64
%154 = llvm.mlir.addressof @MU : !llvm.ptr
%155 = llvm.load %154 : !llvm.ptr -> i64
%156 = llvm.mlir.addressof @LAM : !llvm.ptr
%157 = llvm.load %156 : !llvm.ptr -> i64
%158 = arith.addi %155, %157 : i64
%160 = arith.constant 8 : i32
%161 = arith.extsi %160 : i32 to i64
%159 = func.call @calloc(%158, %161) : (i64, i64) -> !llvm.ptr
%162 = llvm.mlir.zero : !llvm.ptr
%163 = llvm.icmp "eq" %159, %162 : !llvm.ptr
cf.cond_br %163, ^bb24, ^bb25
^bb24:
%164 = arith.constant 1 : i32
func.return %164 : i32
^bb25:
cf.br ^bb26
^bb26:
%165 = arith.constant 0 : i32
%166 = arith.constant 0 : i32
%167 = arith.extsi %165 : i32 to i64
%168 = arith.extsi %166 : i32 to i64
%169 = llvm.getelementptr %159[%168] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %167, %169 : i64, !llvm.ptr
%170 = arith.constant 0 : i32
%171 = arith.extsi %170 : i32 to i64
%172 = llvm.mlir.constant(1 : i64) : i64
%173 = llvm.alloca %172 x i64 : (i64) -> !llvm.ptr
llvm.store %171, %173 : i64, !llvm.ptr
%174 = arith.constant 1 : i32
%175 = arith.extsi %174 : i32 to i64
%176 = llvm.mlir.constant(1 : i64) : i64
%177 = llvm.alloca %176 x i64 : (i64) -> !llvm.ptr
llvm.store %175, %177 : i64, !llvm.ptr
cf.br ^bb27
^bb27:
%178 = llvm.load %177 : !llvm.ptr -> i64
%179 = arith.cmpi slt, %178, %158 : i64
cf.cond_br %179, ^bb28, ^bb29
^bb28:
%181 = llvm.load %173 : !llvm.ptr -> i64
%180 = func.call @next_s(%181) : (i64) -> i64
llvm.store %180, %173 : i64, !llvm.ptr
%182 = llvm.load %173 : !llvm.ptr -> i64
%183 = llvm.load %177 : !llvm.ptr -> i64
%184 = llvm.getelementptr %159[%183] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %182, %184 : i64, !llvm.ptr
%185 = llvm.load %177 : !llvm.ptr -> i64
%186 = arith.constant 1 : i32
%188 = arith.extsi %186 : i32 to i64
%187 = arith.addi %185, %188 : i64
llvm.store %187, %177 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%189 = llvm.mlir.addressof @N : !llvm.ptr
%190 = llvm.load %189 : !llvm.ptr -> i64
%191 = llvm.mlir.constant(1 : i64) : i64
%192 = llvm.alloca %191 x i64 : (i64) -> !llvm.ptr
llvm.store %190, %192 : i64, !llvm.ptr
%193 = arith.constant 0 : i32
%194 = arith.extsi %193 : i32 to i64
%195 = llvm.mlir.constant(1 : i64) : i64
%196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
llvm.store %194, %196 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%197 = llvm.load %192 : !llvm.ptr -> i64
%198 = arith.cmpi sgt, %197, %153 : i64
cf.cond_br %198, ^bb31, ^bb32
^bb31:
%200 = llvm.load %192 : !llvm.ptr -> i64
%201 = llvm.mlir.addressof @MU : !llvm.ptr
%202 = llvm.load %201 : !llvm.ptr -> i64
%203 = llvm.mlir.addressof @LAM : !llvm.ptr
%204 = llvm.load %203 : !llvm.ptr -> i64
%199 = func.call @value_at(%200, %159, %202, %204) : (i64, !llvm.ptr, i64, i64) -> i64
%206 = llvm.load %192 : !llvm.ptr -> i64
%207 = arith.subi %206, %153 : i64
%208 = llvm.mlir.addressof @MU : !llvm.ptr
%209 = llvm.load %208 : !llvm.ptr -> i64
%210 = llvm.mlir.addressof @LAM : !llvm.ptr
%211 = llvm.load %210 : !llvm.ptr -> i64
%205 = func.call @value_at(%207, %159, %209, %211) : (i64, !llvm.ptr, i64, i64) -> i64
%212 = arith.cmpi ne, %199, %205 : i64
cf.cond_br %212, ^bb33, ^bb34
^bb33:
cf.br ^bb32
^bb34:
cf.br ^bb35
^bb35:
%213 = llvm.load %192 : !llvm.ptr -> i64
%214 = arith.subi %213, %153 : i64
llvm.store %214, %192 : i64, !llvm.ptr
%215 = llvm.load %196 : !llvm.ptr -> i64
%216 = arith.constant 1 : i32
%218 = arith.extsi %216 : i32 to i64
%217 = arith.addi %215, %218 : i64
llvm.store %217, %196 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%220 = llvm.load %192 : !llvm.ptr -> i64
%221 = arith.constant 8 : i32
%222 = arith.extsi %221 : i32 to i64
%219 = func.call @calloc(%220, %222) : (i64, i64) -> !llvm.ptr
%223 = llvm.mlir.zero : !llvm.ptr
%224 = llvm.icmp "eq" %219, %223 : !llvm.ptr
cf.cond_br %224, ^bb36, ^bb37
^bb36:
%225 = arith.constant 1 : i32
func.return %225 : i32
^bb37:
cf.br ^bb38
^bb38:
%226 = arith.constant 0 : i32
%227 = arith.extsi %226 : i32 to i64
%228 = llvm.mlir.constant(1 : i64) : i64
%229 = llvm.alloca %228 x i64 : (i64) -> !llvm.ptr
llvm.store %227, %229 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%230 = llvm.load %229 : !llvm.ptr -> i64
%231 = llvm.load %192 : !llvm.ptr -> i64
%232 = arith.cmpi slt, %230, %231 : i64
cf.cond_br %232, ^bb40, ^bb41
^bb40:
%234 = llvm.load %229 : !llvm.ptr -> i64
%235 = arith.constant 1 : i32
%237 = arith.extsi %235 : i32 to i64
%236 = arith.addi %234, %237 : i64
%238 = llvm.mlir.addressof @MU : !llvm.ptr
%239 = llvm.load %238 : !llvm.ptr -> i64
%240 = llvm.mlir.addressof @LAM : !llvm.ptr
%241 = llvm.load %240 : !llvm.ptr -> i64
%233 = func.call @value_at(%236, %159, %239, %241) : (i64, !llvm.ptr, i64, i64) -> i64
%242 = llvm.load %229 : !llvm.ptr -> i64
%243 = llvm.getelementptr %219[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %233, %243 : i64, !llvm.ptr
%244 = llvm.load %229 : !llvm.ptr -> i64
%245 = arith.constant 1 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.addi %244, %247 : i64
llvm.store %246, %229 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
%249 = llvm.load %192 : !llvm.ptr -> i64
%248 = func.call @optimal_first_sum(%219, %249) : (!llvm.ptr, i64) -> i64
func.call @free(%219) : (!llvm.ptr) -> ()
%251 = llvm.load %192 : !llvm.ptr -> i64
%252 = arith.constant 1 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.addi %251, %254 : i64
%255 = arith.constant 1 : i32
%257 = arith.extsi %255 : i32 to i64
%256 = arith.andi %253, %257 : i64
%258 = arith.constant 0 : i32
%259 = arith.extsi %258 : i32 to i64
%260 = llvm.mlir.constant(1 : i64) : i64
%261 = llvm.alloca %260 x i64 : (i64) -> !llvm.ptr
llvm.store %259, %261 : i64, !llvm.ptr
%262 = llvm.load %192 : !llvm.ptr -> i64
%263 = arith.constant 1 : i32
%265 = arith.extsi %263 : i32 to i64
%264 = arith.addi %262, %265 : i64
%266 = llvm.load %192 : !llvm.ptr -> i64
%267 = arith.addi %266, %153 : i64
%268 = llvm.mlir.constant(1 : i64) : i64
%269 = llvm.alloca %268 x i64 : (i64) -> !llvm.ptr
llvm.store %264, %269 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%270 = llvm.load %269 : !llvm.ptr -> i64
%271 = arith.cmpi sle, %270, %267 : i64
cf.cond_br %271, ^bb43, ^bb44
^bb43:
%272 = llvm.load %269 : !llvm.ptr -> i64
%273 = arith.constant 1 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.andi %272, %275 : i64
%276 = arith.cmpi eq, %274, %256 : i64
cf.cond_br %276, ^bb45, ^bb46
^bb45:
%277 = llvm.load %261 : !llvm.ptr -> i64
%279 = llvm.load %269 : !llvm.ptr -> i64
%280 = llvm.mlir.addressof @MU : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> i64
%282 = llvm.mlir.addressof @LAM : !llvm.ptr
%283 = llvm.load %282 : !llvm.ptr -> i64
%278 = func.call @value_at(%279, %159, %281, %283) : (i64, !llvm.ptr, i64, i64) -> i64
%284 = arith.addi %277, %278 : i64
llvm.store %284, %261 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%285 = llvm.load %269 : !llvm.ptr -> i64
%286 = arith.constant 1 : i32
%288 = arith.extsi %286 : i32 to i64
%287 = arith.addi %285, %288 : i64
llvm.store %287, %269 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%289 = llvm.load %196 : !llvm.ptr -> i64
%290 = llvm.load %261 : !llvm.ptr -> i64
%291 = arith.muli %289, %290 : i64
%292 = arith.addi %248, %291 : i64
%293 = llvm.mlir.addressof @str_0 : !llvm.ptr
%294 = llvm.call @printf(%293, %292) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%159) : (!llvm.ptr) -> ()
%296 = arith.constant 0 : i32
func.return %296 : i32
}
}