← All problems Problem 579
Lattice Points in Lattice Cubes — primary quaternion enumeration + Ehrhart sums.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^4)O(n^2)Space complexity O(n)O(n^2)Approach Flow solution Combinatorial or DP counting Verdict Suboptimal
Flow source
# Project Euler 579
# Lattice Points in Lattice Cubes — primary quaternion enumeration + Ehrhart sums.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function igcd(a0: i64, b0: i64) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
if a < 0 { a = -a }
if b < 0 { b = -b }
while b != 0 {
let t: i64 = a % b
a = b
b = t
}
return a
}
function isqrt(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut x: i64 = n
let mut y: i64 = (x + 1) / 2
while y < x {
x = y
y = (x + n / x) / 2
}
return x
}
function iabs(x: i64) -> i64 {
if x < 0 { return -x }
return x
}
function solve_S_mod(n: i64, M: i64) -> i64 {
let sums: ptr<i64> = calloc(7 * (n + 1), 8)
if sums == null { return -1 }
let mut t: i64 = 1
while t <= n {
sums[0 * (n + 1) + t] = t % M
let mut p: i64 = t % M
sums[1 * (n + 1) + t] = (sums[1 * (n + 1) + (t - 1)] + p) % M
let mut k: i64 = 2
while k <= 6 {
p = ((p as i128) * (t as i128) % (M as i128)) as i64
sums[k * (n + 1) + t] = (sums[k * (n + 1) + (t - 1)] + p) % M
k = k + 1
}
t = t + 1
}
let A: i64 = n + 1
let A2: i64 = A * A
let A3: i64 = A2 * A
let mut totalS: i64 = 0
let B: i64 = isqrt(n)
let mut case_i: i64 = 0
while case_i < 2 {
let mut a_parity: i64 = 0
let mut s_limit: i64 = n
let mut start: i64 = -B
if case_i == 0 {
a_parity = 1
s_limit = n - 1
if (B & 1) == 0 {
start = -B
} else {
start = -B + 1
}
} else {
a_parity = 0
s_limit = n
if (B & 1) == 1 {
start = -B
} else {
start = -B + 1
}
}
let mut b: i64 = start
while b <= B {
let bb: i64 = b * b
let mut c: i64 = start
while c <= B {
let cc: i64 = c * c
let bc2: i64 = bb + cc
let mut d: i64 = start
while d <= B {
let dd: i64 = d * d
let s: i64 = bc2 + dd
if s <= s_limit {
let rem: i64 = n - s
let max_a: i64 = isqrt(rem)
let sum_bcd_mod4: i64 = (b + c + d) & 3
let a_res: i64 = (1 - sum_bcd_mod4) & 3
let g_bcd: i64 = igcd(igcd(iabs(b), iabs(c)), iabs(d))
let mut a: i64 = -max_a
while a <= max_a {
if (a & 1) == a_parity && (a & 3) == a_res {
if igcd(g_bcd, iabs(a)) == 1 {
let aa: i64 = a * a
let m: i64 = aa + s
let u0: i64 = aa + bb - cc - dd
let u1: i64 = 2 * (b * c - a * d)
let u2: i64 = 2 * (b * d + a * c)
let v0: i64 = 2 * (b * c + a * d)
let v1: i64 = aa - bb + cc - dd
let v2: i64 = 2 * (c * d - a * b)
let w0: i64 = 2 * (b * d - a * c)
let w1: i64 = 2 * (c * d + a * b)
let w2: i64 = aa - bb - cc + dd
let sx: i64 = iabs(u0) + iabs(v0) + iabs(w0)
let sy: i64 = iabs(u1) + iabs(v1) + iabs(w1)
let sz: i64 = iabs(u2) + iabs(v2) + iabs(w2)
let mut T: i64 = n / sx
let ty: i64 = n / sy
if ty < T { T = ty }
let tz: i64 = n / sz
if tz < T { T = tz }
if T > 0 {
let s1: i64 = sx + sy + sz
let s2v: i64 = sx * sy + sy * sz + sz * sx
let s3: i64 = sx * sy * sz
let t0: i64 = A3 % M
let t1: i64 = ((-A2 * s1) % M + M) % M
let t2: i64 = (A * s2v) % M
let t3: i64 = ((-s3) % M + M) % M
let gU: i64 = igcd(iabs(u0), igcd(iabs(u1), iabs(u2)))
let gV: i64 = igcd(iabs(v0), igcd(iabs(v1), iabs(v2)))
let gW: i64 = igcd(iabs(w0), igcd(iabs(w1), iabs(w2)))
let G1: i64 = gU + gV + gW
let p1: i64 = G1 % M
let p2: i64 = (m * G1) % M
let mm: i64 = m % M
let p3: i64 = ((((mm as i128) * (mm as i128) % (M as i128)) * (mm as i128)) % (M as i128)) as i64
let s0: i64 = T % M
let S1p: i64 = sums[1 * (n + 1) + T]
let S2p: i64 = sums[2 * (n + 1) + T]
let S3p: i64 = sums[3 * (n + 1) + T]
let S4p: i64 = sums[4 * (n + 1) + T]
let S5p: i64 = sums[5 * (n + 1) + T]
let S6p: i64 = sums[6 * (n + 1) + T]
let D0: i64 = t0
let D1: i64 = (t0 * p1 + t1) % M
let D2: i64 = (t0 * p2 + t1 * p1 + t2) % M
let D3: i64 = (t0 * p3 + t1 * p2 + t2 * p1 + t3) % M
let D4: i64 = (t1 * p3 + t2 * p2 + t3 * p1) % M
let D5: i64 = (t2 * p3 + t3 * p2) % M
let D6: i64 = (t3 * p3) % M
totalS = (((((((totalS + D0 * s0) % M + D1 * S1p) % M + D2 * S2p) % M + D3 * S3p) % M + D4 * S4p) % M + D5 * S5p) % M + D6 * S6p) % M
}
}
}
a = a + 1
}
}
d = d + 2
}
c = c + 2
}
b = b + 2
}
case_i = case_i + 1
}
free(sums)
return totalS
}
function main() -> i32 {
printf("%lld\n", solve_S_mod(5000, 1000000000))
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 igcd_i64_i64(int64_t a0, int64_t b0);
int64_t isqrt_i64(int64_t n);
int64_t iabs_i64(int64_t x);
int64_t solve_S_mod_i64_i64(int64_t n, int64_t M);
int32_t main(void);
int64_t igcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
if (a < 0) {
a = (-a);
}
if (b < 0) {
b = (-b);
}
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t isqrt_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t iabs_i64(int64_t x) {
if (x < 0) {
return (-x);
}
return x;
}
int64_t solve_S_mod_i64_i64(int64_t n, int64_t M) {
int64_t* sums = (int64_t*)(calloc((7 * (n + 1)), 8));
if (sums == NULL) {
return (-1);
}
int64_t t = 1;
while (t <= n) {
sums[((0 * (n + 1)) + t)] = FLOW_CHECKED_MOD((t), (M));
int64_t p = FLOW_CHECKED_MOD((t), (M));
sums[((1 * (n + 1)) + t)] = FLOW_CHECKED_MOD(((sums[((1 * (n + 1)) + (t - 1))] + p)), (M));
int64_t k = 2;
while (k <= 6) {
p = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(p)) * ((__int128)(t)))), (((__int128)(M))))));
sums[((k * (n + 1)) + t)] = FLOW_CHECKED_MOD(((sums[((k * (n + 1)) + (t - 1))] + p)), (M));
k = (k + 1);
}
t = (t + 1);
}
int64_t A = (n + 1);
int64_t A2 = (A * A);
int64_t A3 = (A2 * A);
int64_t totalS = 0;
int64_t B = isqrt_i64(n);
int64_t case_i = 0;
while (case_i < 2) {
int64_t a_parity = 0;
int64_t s_limit = n;
int64_t start = (-B);
if (case_i == 0) {
a_parity = 1;
s_limit = (n - 1);
if ((B & 1) == 0) {
start = (-B);
} else {
start = ((-B) + 1);
}
} else {
a_parity = 0;
s_limit = n;
if ((B & 1) == 1) {
start = (-B);
} else {
start = ((-B) + 1);
}
}
int64_t b = start;
while (b <= B) {
int64_t bb = (b * b);
int64_t c = start;
while (c <= B) {
int64_t cc = (c * c);
int64_t bc2 = (bb + cc);
int64_t d = start;
while (d <= B) {
int64_t dd = (d * d);
int64_t s = (bc2 + dd);
if (s <= s_limit) {
int64_t rem = (n - s);
int64_t max_a = isqrt_i64(rem);
int64_t sum_bcd_mod4 = (((b + c) + d) & 3);
int64_t a_res = ((1 - sum_bcd_mod4) & 3);
int64_t g_bcd = igcd_i64_i64(igcd_i64_i64(iabs_i64(b), iabs_i64(c)), iabs_i64(d));
int64_t a = (-max_a);
while (a <= max_a) {
if (((a & 1) == a_parity && (a & 3) == a_res)) {
if (igcd_i64_i64(g_bcd, iabs_i64(a)) == 1) {
int64_t aa = (a * a);
int64_t m = (aa + s);
int64_t u0 = (((aa + bb) - cc) - dd);
int64_t u1 = (2 * ((b * c) - (a * d)));
int64_t u2 = (2 * ((b * d) + (a * c)));
int64_t v0 = (2 * ((b * c) + (a * d)));
int64_t v1 = (((aa - bb) + cc) - dd);
int64_t v2 = (2 * ((c * d) - (a * b)));
int64_t w0 = (2 * ((b * d) - (a * c)));
int64_t w1 = (2 * ((c * d) + (a * b)));
int64_t w2 = (((aa - bb) - cc) + dd);
int64_t sx = ((iabs_i64(u0) + iabs_i64(v0)) + iabs_i64(w0));
int64_t sy = ((iabs_i64(u1) + iabs_i64(v1)) + iabs_i64(w1));
int64_t sz = ((iabs_i64(u2) + iabs_i64(v2)) + iabs_i64(w2));
int64_t T = FLOW_CHECKED_DIV((n), (sx));
int64_t ty = FLOW_CHECKED_DIV((n), (sy));
if (ty < T) {
T = ty;
}
int64_t tz = FLOW_CHECKED_DIV((n), (sz));
if (tz < T) {
T = tz;
}
if (T > 0) {
int64_t s1 = ((sx + sy) + sz);
int64_t s2v = (((sx * sy) + (sy * sz)) + (sz * sx));
int64_t s3 = ((sx * sy) * sz);
int64_t t0 = FLOW_CHECKED_MOD((A3), (M));
int64_t t1 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((-A2) * s1)), (M)) + M)), (M));
int64_t t2 = FLOW_CHECKED_MOD(((A * s2v)), (M));
int64_t t3 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((-s3)), (M)) + M)), (M));
int64_t gU = igcd_i64_i64(iabs_i64(u0), igcd_i64_i64(iabs_i64(u1), iabs_i64(u2)));
int64_t gV = igcd_i64_i64(iabs_i64(v0), igcd_i64_i64(iabs_i64(v1), iabs_i64(v2)));
int64_t gW = igcd_i64_i64(iabs_i64(w0), igcd_i64_i64(iabs_i64(w1), iabs_i64(w2)));
int64_t G1 = ((gU + gV) + gW);
int64_t p1 = FLOW_CHECKED_MOD((G1), (M));
int64_t p2 = FLOW_CHECKED_MOD(((m * G1)), (M));
int64_t mm = FLOW_CHECKED_MOD((m), (M));
int64_t p3 = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((__int128)(mm)) * ((__int128)(mm)))), (((__int128)(M)))) * ((__int128)(mm)))), (((__int128)(M))))));
int64_t s0 = FLOW_CHECKED_MOD((T), (M));
int64_t S1p = sums[((1 * (n + 1)) + T)];
int64_t S2p = sums[((2 * (n + 1)) + T)];
int64_t S3p = sums[((3 * (n + 1)) + T)];
int64_t S4p = sums[((4 * (n + 1)) + T)];
int64_t S5p = sums[((5 * (n + 1)) + T)];
int64_t S6p = sums[((6 * (n + 1)) + T)];
int64_t D0 = t0;
int64_t D1 = FLOW_CHECKED_MOD((((t0 * p1) + t1)), (M));
int64_t D2 = FLOW_CHECKED_MOD(((((t0 * p2) + (t1 * p1)) + t2)), (M));
int64_t D3 = FLOW_CHECKED_MOD((((((t0 * p3) + (t1 * p2)) + (t2 * p1)) + t3)), (M));
int64_t D4 = FLOW_CHECKED_MOD(((((t1 * p3) + (t2 * p2)) + (t3 * p1))), (M));
int64_t D5 = FLOW_CHECKED_MOD((((t2 * p3) + (t3 * p2))), (M));
int64_t D6 = FLOW_CHECKED_MOD(((t3 * p3)), (M));
totalS = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((totalS + (D0 * s0))), (M)) + (D1 * S1p))), (M)) + (D2 * S2p))), (M)) + (D3 * S3p))), (M)) + (D4 * S4p))), (M)) + (D5 * S5p))), (M)) + (D6 * S6p))), (M));
}
}
}
a = (a + 1);
}
}
d = (d + 2);
}
c = (c + 2);
}
b = (b + 2);
}
case_i = (case_i + 1);
}
free(sums);
return totalS;
}
int32_t main(void) {
printf("%lld\n", solve_S_mod_i64_i64(5000, 1000000000));
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 @igcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
%4 = llvm.load %1 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi slt, %4, %7 : i64
cf.cond_br %6, ^bb0, ^bb1
^bb0:
%8 = llvm.load %1 : !llvm.ptr -> i64
%10 = arith.constant 0 : i64
%9 = arith.subi %10, %8 : i64
llvm.store %9, %1 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%11 = llvm.load %3 : !llvm.ptr -> i64
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi slt, %11, %14 : i64
cf.cond_br %13, ^bb3, ^bb4
^bb3:
%15 = llvm.load %3 : !llvm.ptr -> i64
%17 = arith.constant 0 : i64
%16 = arith.subi %17, %15 : i64
llvm.store %16, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%18 = llvm.load %3 : !llvm.ptr -> i64
%19 = arith.constant 0 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi ne, %18, %21 : i64
cf.cond_br %20, ^bb7, ^bb8
^bb7:
%22 = llvm.load %1 : !llvm.ptr -> i64
%23 = llvm.load %3 : !llvm.ptr -> i64
%24 = arith.remsi %22, %23 : i64
%25 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %25, %1 : i64, !llvm.ptr
llvm.store %24, %3 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%26 = llvm.load %1 : !llvm.ptr -> i64
func.return %26 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%27 = arith.constant 0 : i32
%29 = arith.extsi %27 : i32 to i64
%28 = arith.cmpi sle, %arg0, %29 : i64
cf.cond_br %28, ^bb9, ^bb10
^bb9:
%30 = arith.constant 0 : i32
%31 = arith.extsi %30 : i32 to i64
func.return %31 : i64
^bb10:
cf.br ^bb11
^bb11:
%32 = llvm.mlir.constant(1 : i64) : i64
%33 = llvm.alloca %32 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %33 : i64, !llvm.ptr
%34 = llvm.load %33 : !llvm.ptr -> i64
%35 = arith.constant 1 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.addi %34, %37 : i64
%38 = arith.constant 2 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.divsi %36, %40 : i64
%41 = llvm.mlir.constant(1 : i64) : i64
%42 = llvm.alloca %41 x i64 : (i64) -> !llvm.ptr
llvm.store %39, %42 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%43 = llvm.load %42 : !llvm.ptr -> i64
%44 = llvm.load %33 : !llvm.ptr -> i64
%45 = arith.cmpi slt, %43, %44 : i64
cf.cond_br %45, ^bb13, ^bb14
^bb13:
%46 = llvm.load %42 : !llvm.ptr -> i64
llvm.store %46, %33 : i64, !llvm.ptr
%47 = llvm.load %33 : !llvm.ptr -> i64
%48 = llvm.load %33 : !llvm.ptr -> i64
%49 = arith.divsi %arg0, %48 : i64
%50 = arith.addi %47, %49 : i64
%51 = arith.constant 2 : i32
%53 = arith.extsi %51 : i32 to i64
%52 = arith.divsi %50, %53 : i64
llvm.store %52, %42 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%54 = llvm.load %33 : !llvm.ptr -> i64
func.return %54 : i64
}
func.func @iabs(%arg0: i64) -> i64 {
%55 = arith.constant 0 : i32
%57 = arith.extsi %55 : i32 to i64
%56 = arith.cmpi slt, %arg0, %57 : i64
cf.cond_br %56, ^bb15, ^bb16
^bb15:
%59 = arith.constant 0 : i64
%58 = arith.subi %59, %arg0 : i64
func.return %58 : i64
^bb16:
cf.br ^bb17
^bb17:
func.return %arg0 : i64
}
func.func @solve_S_mod(%arg0: i64, %arg1: i64) -> i64 {
%61 = arith.constant 7 : i32
%62 = arith.constant 1 : i32
%64 = arith.extsi %62 : i32 to i64
%63 = arith.addi %arg0, %64 : i64
%66 = arith.extsi %61 : i32 to i64
%65 = arith.muli %66, %63 : i64
%67 = arith.constant 8 : i32
%68 = arith.extsi %67 : i32 to i64
%60 = func.call @calloc(%65, %68) : (i64, i64) -> !llvm.ptr
%69 = llvm.mlir.zero : !llvm.ptr
%70 = llvm.icmp "eq" %60, %69 : !llvm.ptr
cf.cond_br %70, ^bb18, ^bb19
^bb18:
%71 = arith.constant 1 : i32
%73 = arith.constant 0 : i32
%72 = arith.subi %73, %71 : i32
%74 = arith.extsi %72 : i32 to i64
func.return %74 : i64
^bb19:
cf.br ^bb20
^bb20:
%75 = arith.constant 1 : i32
%76 = arith.extsi %75 : i32 to i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%79 = llvm.load %78 : !llvm.ptr -> i64
%80 = arith.cmpi sle, %79, %arg0 : i64
cf.cond_br %80, ^bb22, ^bb23
^bb22:
%81 = llvm.load %78 : !llvm.ptr -> i64
%82 = arith.remsi %81, %arg1 : i64
%83 = arith.constant 0 : i32
%84 = arith.constant 1 : i32
%86 = arith.extsi %84 : i32 to i64
%85 = arith.addi %arg0, %86 : i64
%88 = arith.extsi %83 : i32 to i64
%87 = arith.muli %88, %85 : i64
%89 = llvm.load %78 : !llvm.ptr -> i64
%90 = arith.addi %87, %89 : i64
%91 = llvm.getelementptr %60[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %82, %91 : i64, !llvm.ptr
%92 = llvm.load %78 : !llvm.ptr -> i64
%93 = arith.remsi %92, %arg1 : i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%97 = arith.constant 1 : i32
%98 = arith.constant 1 : i32
%100 = arith.extsi %98 : i32 to i64
%99 = arith.addi %arg0, %100 : i64
%102 = arith.extsi %97 : i32 to i64
%101 = arith.muli %102, %99 : i64
%103 = llvm.load %78 : !llvm.ptr -> i64
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.subi %103, %106 : i64
%107 = arith.addi %101, %105 : i64
%108 = llvm.getelementptr %60[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%96 = llvm.load %108 : !llvm.ptr -> i64
%109 = llvm.load %95 : !llvm.ptr -> i64
%110 = arith.addi %96, %109 : i64
%111 = arith.remsi %110, %arg1 : i64
%112 = arith.constant 1 : i32
%113 = arith.constant 1 : i32
%115 = arith.extsi %113 : i32 to i64
%114 = arith.addi %arg0, %115 : i64
%117 = arith.extsi %112 : i32 to i64
%116 = arith.muli %117, %114 : i64
%118 = llvm.load %78 : !llvm.ptr -> i64
%119 = arith.addi %116, %118 : i64
%120 = llvm.getelementptr %60[%119] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %111, %120 : i64, !llvm.ptr
%121 = arith.constant 2 : i32
%122 = arith.extsi %121 : i32 to i64
%123 = llvm.mlir.constant(1 : i64) : i64
%124 = llvm.alloca %123 x i64 : (i64) -> !llvm.ptr
llvm.store %122, %124 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%125 = llvm.load %124 : !llvm.ptr -> i64
%126 = arith.constant 6 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.cmpi sle, %125, %128 : i64
cf.cond_br %127, ^bb25, ^bb26
^bb25:
%129 = llvm.load %95 : !llvm.ptr -> i64
%130 = arith.extsi %129 : i64 to i128
%131 = llvm.load %78 : !llvm.ptr -> i64
%132 = arith.extsi %131 : i64 to i128
%134 = arith.trunci %130 : i128 to i64
%135 = arith.trunci %132 : i128 to i64
%133 = arith.muli %134, %135 : i64
%136 = arith.extsi %arg1 : i64 to i128
%138 = arith.trunci %136 : i128 to i64
%137 = arith.remsi %133, %138 : i64
llvm.store %137, %95 : i64, !llvm.ptr
%140 = llvm.load %124 : !llvm.ptr -> i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.addi %arg0, %143 : i64
%144 = arith.muli %140, %142 : i64
%145 = llvm.load %78 : !llvm.ptr -> i64
%146 = arith.constant 1 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.subi %145, %148 : i64
%149 = arith.addi %144, %147 : i64
%150 = llvm.getelementptr %60[%149] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%139 = llvm.load %150 : !llvm.ptr -> i64
%151 = llvm.load %95 : !llvm.ptr -> i64
%152 = arith.addi %139, %151 : i64
%153 = arith.remsi %152, %arg1 : i64
%154 = llvm.load %124 : !llvm.ptr -> i64
%155 = arith.constant 1 : i32
%157 = arith.extsi %155 : i32 to i64
%156 = arith.addi %arg0, %157 : i64
%158 = arith.muli %154, %156 : i64
%159 = llvm.load %78 : !llvm.ptr -> i64
%160 = arith.addi %158, %159 : i64
%161 = llvm.getelementptr %60[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %153, %161 : i64, !llvm.ptr
%162 = llvm.load %124 : !llvm.ptr -> i64
%163 = arith.constant 1 : i32
%165 = arith.extsi %163 : i32 to i64
%164 = arith.addi %162, %165 : i64
llvm.store %164, %124 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%166 = llvm.load %78 : !llvm.ptr -> i64
%167 = arith.constant 1 : i32
%169 = arith.extsi %167 : i32 to i64
%168 = arith.addi %166, %169 : i64
llvm.store %168, %78 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%170 = arith.constant 1 : i32
%172 = arith.extsi %170 : i32 to i64
%171 = arith.addi %arg0, %172 : i64
%173 = arith.muli %171, %171 : i64
%174 = arith.muli %173, %171 : i64
%175 = arith.constant 0 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i64, !llvm.ptr
%179 = func.call @isqrt(%arg0) : (i64) -> 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
cf.br ^bb27
^bb27:
%184 = llvm.load %183 : !llvm.ptr -> i64
%185 = arith.constant 2 : i32
%187 = arith.extsi %185 : i32 to i64
%186 = arith.cmpi slt, %184, %187 : i64
cf.cond_br %186, ^bb28, ^bb29
^bb28:
%188 = arith.constant 0 : i32
%189 = arith.extsi %188 : i32 to i64
%190 = llvm.mlir.constant(1 : i64) : i64
%191 = llvm.alloca %190 x i64 : (i64) -> !llvm.ptr
llvm.store %189, %191 : i64, !llvm.ptr
%192 = llvm.mlir.constant(1 : i64) : i64
%193 = llvm.alloca %192 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %193 : i64, !llvm.ptr
%195 = arith.constant 0 : i64
%194 = arith.subi %195, %179 : i64
%196 = llvm.mlir.constant(1 : i64) : i64
%197 = llvm.alloca %196 x i64 : (i64) -> !llvm.ptr
llvm.store %194, %197 : i64, !llvm.ptr
%198 = llvm.load %183 : !llvm.ptr -> i64
%199 = arith.constant 0 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.cmpi eq, %198, %201 : i64
cf.cond_br %200, ^bb30, ^bb31
^bb30:
%202 = arith.constant 1 : i32
%203 = arith.extsi %202 : i32 to i64
llvm.store %203, %191 : i64, !llvm.ptr
%204 = arith.constant 1 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.subi %arg0, %206 : i64
llvm.store %205, %193 : i64, !llvm.ptr
%207 = arith.constant 1 : i32
%209 = arith.extsi %207 : i32 to i64
%208 = arith.andi %179, %209 : i64
%210 = arith.constant 0 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.cmpi eq, %208, %212 : i64
cf.cond_br %211, ^bb33, ^bb34
^bb33:
%214 = arith.constant 0 : i64
%213 = arith.subi %214, %179 : i64
llvm.store %213, %197 : i64, !llvm.ptr
cf.br ^bb35
^bb34:
%216 = arith.constant 0 : i64
%215 = arith.subi %216, %179 : i64
%217 = arith.constant 1 : i32
%219 = arith.extsi %217 : i32 to i64
%218 = arith.addi %215, %219 : i64
llvm.store %218, %197 : i64, !llvm.ptr
cf.br ^bb35
^bb35:
cf.br ^bb32
^bb31:
%220 = arith.constant 0 : i32
%221 = arith.extsi %220 : i32 to i64
llvm.store %221, %191 : i64, !llvm.ptr
llvm.store %arg0, %193 : i64, !llvm.ptr
%222 = arith.constant 1 : i32
%224 = arith.extsi %222 : i32 to i64
%223 = arith.andi %179, %224 : i64
%225 = arith.constant 1 : i32
%227 = arith.extsi %225 : i32 to i64
%226 = arith.cmpi eq, %223, %227 : i64
cf.cond_br %226, ^bb36, ^bb37
^bb36:
%229 = arith.constant 0 : i64
%228 = arith.subi %229, %179 : i64
llvm.store %228, %197 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
%231 = arith.constant 0 : i64
%230 = arith.subi %231, %179 : i64
%232 = arith.constant 1 : i32
%234 = arith.extsi %232 : i32 to i64
%233 = arith.addi %230, %234 : i64
llvm.store %233, %197 : i64, !llvm.ptr
cf.br ^bb38
^bb38:
cf.br ^bb32
^bb32:
%235 = llvm.load %197 : !llvm.ptr -> i64
%236 = llvm.mlir.constant(1 : i64) : i64
%237 = llvm.alloca %236 x i64 : (i64) -> !llvm.ptr
llvm.store %235, %237 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%238 = llvm.load %237 : !llvm.ptr -> i64
%239 = arith.cmpi sle, %238, %179 : i64
cf.cond_br %239, ^bb40, ^bb41
^bb40:
%240 = llvm.load %237 : !llvm.ptr -> i64
%241 = llvm.load %237 : !llvm.ptr -> i64
%242 = arith.muli %240, %241 : i64
%243 = llvm.load %197 : !llvm.ptr -> i64
%244 = llvm.mlir.constant(1 : i64) : i64
%245 = llvm.alloca %244 x i64 : (i64) -> !llvm.ptr
llvm.store %243, %245 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%246 = llvm.load %245 : !llvm.ptr -> i64
%247 = arith.cmpi sle, %246, %179 : i64
cf.cond_br %247, ^bb43, ^bb44
^bb43:
%248 = llvm.load %245 : !llvm.ptr -> i64
%249 = llvm.load %245 : !llvm.ptr -> i64
%250 = arith.muli %248, %249 : i64
%251 = arith.addi %242, %250 : i64
%252 = llvm.load %197 : !llvm.ptr -> i64
%253 = llvm.mlir.constant(1 : i64) : i64
%254 = llvm.alloca %253 x i64 : (i64) -> !llvm.ptr
llvm.store %252, %254 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%255 = llvm.load %254 : !llvm.ptr -> i64
%256 = arith.cmpi sle, %255, %179 : i64
cf.cond_br %256, ^bb46, ^bb47
^bb46:
%257 = llvm.load %254 : !llvm.ptr -> i64
%258 = llvm.load %254 : !llvm.ptr -> i64
%259 = arith.muli %257, %258 : i64
%260 = arith.addi %251, %259 : i64
%261 = llvm.load %193 : !llvm.ptr -> i64
%262 = arith.cmpi sle, %260, %261 : i64
cf.cond_br %262, ^bb48, ^bb49
^bb48:
%263 = arith.subi %arg0, %260 : i64
%264 = func.call @isqrt(%263) : (i64) -> i64
%265 = llvm.load %237 : !llvm.ptr -> i64
%266 = llvm.load %245 : !llvm.ptr -> i64
%267 = arith.addi %265, %266 : i64
%268 = llvm.load %254 : !llvm.ptr -> i64
%269 = arith.addi %267, %268 : i64
%270 = arith.constant 3 : i32
%272 = arith.extsi %270 : i32 to i64
%271 = arith.andi %269, %272 : i64
%273 = arith.constant 1 : i32
%275 = arith.extsi %273 : i32 to i64
%274 = arith.subi %275, %271 : i64
%276 = arith.constant 3 : i32
%278 = arith.extsi %276 : i32 to i64
%277 = arith.andi %274, %278 : i64
%282 = llvm.load %237 : !llvm.ptr -> i64
%281 = func.call @iabs(%282) : (i64) -> i64
%284 = llvm.load %245 : !llvm.ptr -> i64
%283 = func.call @iabs(%284) : (i64) -> i64
%280 = func.call @igcd(%281, %283) : (i64, i64) -> i64
%286 = llvm.load %254 : !llvm.ptr -> i64
%285 = func.call @iabs(%286) : (i64) -> i64
%279 = func.call @igcd(%280, %285) : (i64, i64) -> i64
%288 = arith.constant 0 : i64
%287 = arith.subi %288, %264 : i64
%289 = llvm.mlir.constant(1 : i64) : i64
%290 = llvm.alloca %289 x i64 : (i64) -> !llvm.ptr
llvm.store %287, %290 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%291 = llvm.load %290 : !llvm.ptr -> i64
%292 = arith.cmpi sle, %291, %264 : i64
cf.cond_br %292, ^bb52, ^bb53
^bb52:
%293 = llvm.load %290 : !llvm.ptr -> i64
%294 = arith.constant 1 : i32
%296 = arith.extsi %294 : i32 to i64
%295 = arith.andi %293, %296 : i64
%297 = llvm.load %191 : !llvm.ptr -> i64
%298 = arith.cmpi eq, %295, %297 : i64
%299 = scf.if %298 -> (i1) {
%300 = llvm.load %290 : !llvm.ptr -> i64
%301 = arith.constant 3 : i32
%303 = arith.extsi %301 : i32 to i64
%302 = arith.andi %300, %303 : i64
%304 = arith.cmpi eq, %302, %277 : i64
scf.yield %304 : i1
} else {
%305 = arith.constant false
scf.yield %305 : i1
}
cf.cond_br %299, ^bb54, ^bb55
^bb54:
%308 = llvm.load %290 : !llvm.ptr -> i64
%307 = func.call @iabs(%308) : (i64) -> i64
%306 = func.call @igcd(%279, %307) : (i64, i64) -> i64
%309 = arith.constant 1 : i32
%311 = arith.extsi %309 : i32 to i64
%310 = arith.cmpi eq, %306, %311 : i64
cf.cond_br %310, ^bb57, ^bb58
^bb57:
%312 = llvm.load %290 : !llvm.ptr -> i64
%313 = llvm.load %290 : !llvm.ptr -> i64
%314 = arith.muli %312, %313 : i64
%315 = arith.addi %314, %260 : i64
%316 = arith.addi %314, %242 : i64
%317 = arith.subi %316, %250 : i64
%318 = arith.subi %317, %259 : i64
%319 = arith.constant 2 : i32
%320 = llvm.load %237 : !llvm.ptr -> i64
%321 = llvm.load %245 : !llvm.ptr -> i64
%322 = arith.muli %320, %321 : i64
%323 = llvm.load %290 : !llvm.ptr -> i64
%324 = llvm.load %254 : !llvm.ptr -> i64
%325 = arith.muli %323, %324 : i64
%326 = arith.subi %322, %325 : i64
%328 = arith.extsi %319 : i32 to i64
%327 = arith.muli %328, %326 : i64
%329 = arith.constant 2 : i32
%330 = llvm.load %237 : !llvm.ptr -> i64
%331 = llvm.load %254 : !llvm.ptr -> i64
%332 = arith.muli %330, %331 : i64
%333 = llvm.load %290 : !llvm.ptr -> i64
%334 = llvm.load %245 : !llvm.ptr -> i64
%335 = arith.muli %333, %334 : i64
%336 = arith.addi %332, %335 : i64
%338 = arith.extsi %329 : i32 to i64
%337 = arith.muli %338, %336 : i64
%339 = arith.constant 2 : i32
%340 = llvm.load %237 : !llvm.ptr -> i64
%341 = llvm.load %245 : !llvm.ptr -> i64
%342 = arith.muli %340, %341 : i64
%343 = llvm.load %290 : !llvm.ptr -> i64
%344 = llvm.load %254 : !llvm.ptr -> i64
%345 = arith.muli %343, %344 : i64
%346 = arith.addi %342, %345 : i64
%348 = arith.extsi %339 : i32 to i64
%347 = arith.muli %348, %346 : i64
%349 = arith.subi %314, %242 : i64
%350 = arith.addi %349, %250 : i64
%351 = arith.subi %350, %259 : i64
%352 = arith.constant 2 : i32
%353 = llvm.load %245 : !llvm.ptr -> i64
%354 = llvm.load %254 : !llvm.ptr -> i64
%355 = arith.muli %353, %354 : i64
%356 = llvm.load %290 : !llvm.ptr -> i64
%357 = llvm.load %237 : !llvm.ptr -> i64
%358 = arith.muli %356, %357 : i64
%359 = arith.subi %355, %358 : i64
%361 = arith.extsi %352 : i32 to i64
%360 = arith.muli %361, %359 : i64
%362 = arith.constant 2 : i32
%363 = llvm.load %237 : !llvm.ptr -> i64
%364 = llvm.load %254 : !llvm.ptr -> i64
%365 = arith.muli %363, %364 : i64
%366 = llvm.load %290 : !llvm.ptr -> i64
%367 = llvm.load %245 : !llvm.ptr -> i64
%368 = arith.muli %366, %367 : i64
%369 = arith.subi %365, %368 : i64
%371 = arith.extsi %362 : i32 to i64
%370 = arith.muli %371, %369 : i64
%372 = arith.constant 2 : i32
%373 = llvm.load %245 : !llvm.ptr -> i64
%374 = llvm.load %254 : !llvm.ptr -> i64
%375 = arith.muli %373, %374 : i64
%376 = llvm.load %290 : !llvm.ptr -> i64
%377 = llvm.load %237 : !llvm.ptr -> i64
%378 = arith.muli %376, %377 : i64
%379 = arith.addi %375, %378 : i64
%381 = arith.extsi %372 : i32 to i64
%380 = arith.muli %381, %379 : i64
%382 = arith.subi %314, %242 : i64
%383 = arith.subi %382, %250 : i64
%384 = arith.addi %383, %259 : i64
%385 = func.call @iabs(%318) : (i64) -> i64
%386 = func.call @iabs(%347) : (i64) -> i64
%387 = arith.addi %385, %386 : i64
%388 = func.call @iabs(%370) : (i64) -> i64
%389 = arith.addi %387, %388 : i64
%390 = func.call @iabs(%327) : (i64) -> i64
%391 = func.call @iabs(%351) : (i64) -> i64
%392 = arith.addi %390, %391 : i64
%393 = func.call @iabs(%380) : (i64) -> i64
%394 = arith.addi %392, %393 : i64
%395 = func.call @iabs(%337) : (i64) -> i64
%396 = func.call @iabs(%360) : (i64) -> i64
%397 = arith.addi %395, %396 : i64
%398 = func.call @iabs(%384) : (i64) -> i64
%399 = arith.addi %397, %398 : i64
%400 = arith.divsi %arg0, %389 : i64
%401 = llvm.mlir.constant(1 : i64) : i64
%402 = llvm.alloca %401 x i64 : (i64) -> !llvm.ptr
llvm.store %400, %402 : i64, !llvm.ptr
%403 = arith.divsi %arg0, %394 : i64
%404 = llvm.load %402 : !llvm.ptr -> i64
%405 = arith.cmpi slt, %403, %404 : i64
cf.cond_br %405, ^bb60, ^bb61
^bb60:
llvm.store %403, %402 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%406 = arith.divsi %arg0, %399 : i64
%407 = llvm.load %402 : !llvm.ptr -> i64
%408 = arith.cmpi slt, %406, %407 : i64
cf.cond_br %408, ^bb63, ^bb64
^bb63:
llvm.store %406, %402 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
%409 = llvm.load %402 : !llvm.ptr -> i64
%410 = arith.constant 0 : i32
%412 = arith.extsi %410 : i32 to i64
%411 = arith.cmpi sgt, %409, %412 : i64
cf.cond_br %411, ^bb66, ^bb67
^bb66:
%413 = arith.addi %389, %394 : i64
%414 = arith.addi %413, %399 : i64
%415 = arith.muli %389, %394 : i64
%416 = arith.muli %394, %399 : i64
%417 = arith.addi %415, %416 : i64
%418 = arith.muli %399, %389 : i64
%419 = arith.addi %417, %418 : i64
%420 = arith.muli %389, %394 : i64
%421 = arith.muli %420, %399 : i64
%422 = arith.remsi %174, %arg1 : i64
%424 = arith.constant 0 : i64
%423 = arith.subi %424, %173 : i64
%425 = arith.muli %423, %414 : i64
%426 = arith.remsi %425, %arg1 : i64
%427 = arith.addi %426, %arg1 : i64
%428 = arith.remsi %427, %arg1 : i64
%429 = arith.muli %171, %419 : i64
%430 = arith.remsi %429, %arg1 : i64
%432 = arith.constant 0 : i64
%431 = arith.subi %432, %421 : i64
%433 = arith.remsi %431, %arg1 : i64
%434 = arith.addi %433, %arg1 : i64
%435 = arith.remsi %434, %arg1 : i64
%437 = func.call @iabs(%318) : (i64) -> i64
%439 = func.call @iabs(%327) : (i64) -> i64
%440 = func.call @iabs(%337) : (i64) -> i64
%438 = func.call @igcd(%439, %440) : (i64, i64) -> i64
%436 = func.call @igcd(%437, %438) : (i64, i64) -> i64
%442 = func.call @iabs(%347) : (i64) -> i64
%444 = func.call @iabs(%351) : (i64) -> i64
%445 = func.call @iabs(%360) : (i64) -> i64
%443 = func.call @igcd(%444, %445) : (i64, i64) -> i64
%441 = func.call @igcd(%442, %443) : (i64, i64) -> i64
%447 = func.call @iabs(%370) : (i64) -> i64
%449 = func.call @iabs(%380) : (i64) -> i64
%450 = func.call @iabs(%384) : (i64) -> i64
%448 = func.call @igcd(%449, %450) : (i64, i64) -> i64
%446 = func.call @igcd(%447, %448) : (i64, i64) -> i64
%451 = arith.addi %436, %441 : i64
%452 = arith.addi %451, %446 : i64
%453 = arith.remsi %452, %arg1 : i64
%454 = arith.muli %315, %452 : i64
%455 = arith.remsi %454, %arg1 : i64
%456 = arith.remsi %315, %arg1 : i64
%457 = arith.extsi %456 : i64 to i128
%458 = arith.extsi %456 : i64 to i128
%460 = arith.trunci %457 : i128 to i64
%461 = arith.trunci %458 : i128 to i64
%459 = arith.muli %460, %461 : i64
%462 = arith.extsi %arg1 : i64 to i128
%464 = arith.trunci %462 : i128 to i64
%463 = arith.remsi %459, %464 : i64
%465 = arith.extsi %456 : i64 to i128
%467 = arith.trunci %465 : i128 to i64
%466 = arith.muli %463, %467 : i64
%468 = arith.extsi %arg1 : i64 to i128
%470 = arith.trunci %468 : i128 to i64
%469 = arith.remsi %466, %470 : i64
%471 = llvm.load %402 : !llvm.ptr -> i64
%472 = arith.remsi %471, %arg1 : i64
%474 = arith.constant 1 : i32
%475 = arith.constant 1 : i32
%477 = arith.extsi %475 : i32 to i64
%476 = arith.addi %arg0, %477 : i64
%479 = arith.extsi %474 : i32 to i64
%478 = arith.muli %479, %476 : i64
%480 = llvm.load %402 : !llvm.ptr -> i64
%481 = arith.addi %478, %480 : i64
%482 = llvm.getelementptr %60[%481] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%473 = llvm.load %482 : !llvm.ptr -> i64
%484 = arith.constant 2 : i32
%485 = arith.constant 1 : i32
%487 = arith.extsi %485 : i32 to i64
%486 = arith.addi %arg0, %487 : i64
%489 = arith.extsi %484 : i32 to i64
%488 = arith.muli %489, %486 : i64
%490 = llvm.load %402 : !llvm.ptr -> i64
%491 = arith.addi %488, %490 : i64
%492 = llvm.getelementptr %60[%491] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%483 = llvm.load %492 : !llvm.ptr -> i64
%494 = arith.constant 3 : i32
%495 = arith.constant 1 : i32
%497 = arith.extsi %495 : i32 to i64
%496 = arith.addi %arg0, %497 : i64
%499 = arith.extsi %494 : i32 to i64
%498 = arith.muli %499, %496 : i64
%500 = llvm.load %402 : !llvm.ptr -> i64
%501 = arith.addi %498, %500 : i64
%502 = llvm.getelementptr %60[%501] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%493 = llvm.load %502 : !llvm.ptr -> i64
%504 = arith.constant 4 : i32
%505 = arith.constant 1 : i32
%507 = arith.extsi %505 : i32 to i64
%506 = arith.addi %arg0, %507 : i64
%509 = arith.extsi %504 : i32 to i64
%508 = arith.muli %509, %506 : i64
%510 = llvm.load %402 : !llvm.ptr -> i64
%511 = arith.addi %508, %510 : i64
%512 = llvm.getelementptr %60[%511] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%503 = llvm.load %512 : !llvm.ptr -> i64
%514 = arith.constant 5 : i32
%515 = arith.constant 1 : i32
%517 = arith.extsi %515 : i32 to i64
%516 = arith.addi %arg0, %517 : i64
%519 = arith.extsi %514 : i32 to i64
%518 = arith.muli %519, %516 : i64
%520 = llvm.load %402 : !llvm.ptr -> i64
%521 = arith.addi %518, %520 : i64
%522 = llvm.getelementptr %60[%521] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%513 = llvm.load %522 : !llvm.ptr -> i64
%524 = arith.constant 6 : i32
%525 = arith.constant 1 : i32
%527 = arith.extsi %525 : i32 to i64
%526 = arith.addi %arg0, %527 : i64
%529 = arith.extsi %524 : i32 to i64
%528 = arith.muli %529, %526 : i64
%530 = llvm.load %402 : !llvm.ptr -> i64
%531 = arith.addi %528, %530 : i64
%532 = llvm.getelementptr %60[%531] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%523 = llvm.load %532 : !llvm.ptr -> i64
%533 = arith.muli %422, %453 : i64
%534 = arith.addi %533, %428 : i64
%535 = arith.remsi %534, %arg1 : i64
%536 = arith.muli %422, %455 : i64
%537 = arith.muli %428, %453 : i64
%538 = arith.addi %536, %537 : i64
%539 = arith.addi %538, %430 : i64
%540 = arith.remsi %539, %arg1 : i64
%541 = arith.muli %422, %469 : i64
%542 = arith.muli %428, %455 : i64
%543 = arith.addi %541, %542 : i64
%544 = arith.muli %430, %453 : i64
%545 = arith.addi %543, %544 : i64
%546 = arith.addi %545, %435 : i64
%547 = arith.remsi %546, %arg1 : i64
%548 = arith.muli %428, %469 : i64
%549 = arith.muli %430, %455 : i64
%550 = arith.addi %548, %549 : i64
%551 = arith.muli %435, %453 : i64
%552 = arith.addi %550, %551 : i64
%553 = arith.remsi %552, %arg1 : i64
%554 = arith.muli %430, %469 : i64
%555 = arith.muli %435, %455 : i64
%556 = arith.addi %554, %555 : i64
%557 = arith.remsi %556, %arg1 : i64
%558 = arith.muli %435, %469 : i64
%559 = arith.remsi %558, %arg1 : i64
%560 = llvm.load %178 : !llvm.ptr -> i64
%561 = arith.muli %422, %472 : i64
%562 = arith.addi %560, %561 : i64
%563 = arith.remsi %562, %arg1 : i64
%564 = arith.muli %535, %473 : i64
%565 = arith.addi %563, %564 : i64
%566 = arith.remsi %565, %arg1 : i64
%567 = arith.muli %540, %483 : i64
%568 = arith.addi %566, %567 : i64
%569 = arith.remsi %568, %arg1 : i64
%570 = arith.muli %547, %493 : i64
%571 = arith.addi %569, %570 : i64
%572 = arith.remsi %571, %arg1 : i64
%573 = arith.muli %553, %503 : i64
%574 = arith.addi %572, %573 : i64
%575 = arith.remsi %574, %arg1 : i64
%576 = arith.muli %557, %513 : i64
%577 = arith.addi %575, %576 : i64
%578 = arith.remsi %577, %arg1 : i64
%579 = arith.muli %559, %523 : i64
%580 = arith.addi %578, %579 : i64
%581 = arith.remsi %580, %arg1 : i64
llvm.store %581, %178 : i64, !llvm.ptr
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%582 = llvm.load %290 : !llvm.ptr -> i64
%583 = arith.constant 1 : i32
%585 = arith.extsi %583 : i32 to i64
%584 = arith.addi %582, %585 : i64
llvm.store %584, %290 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%586 = llvm.load %254 : !llvm.ptr -> i64
%587 = arith.constant 2 : i32
%589 = arith.extsi %587 : i32 to i64
%588 = arith.addi %586, %589 : i64
llvm.store %588, %254 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%590 = llvm.load %245 : !llvm.ptr -> i64
%591 = arith.constant 2 : i32
%593 = arith.extsi %591 : i32 to i64
%592 = arith.addi %590, %593 : i64
llvm.store %592, %245 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%594 = llvm.load %237 : !llvm.ptr -> i64
%595 = arith.constant 2 : i32
%597 = arith.extsi %595 : i32 to i64
%596 = arith.addi %594, %597 : i64
llvm.store %596, %237 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
%598 = llvm.load %183 : !llvm.ptr -> i64
%599 = arith.constant 1 : i32
%601 = arith.extsi %599 : i32 to i64
%600 = arith.addi %598, %601 : i64
llvm.store %600, %183 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
func.call @free(%60) : (!llvm.ptr) -> ()
%603 = llvm.load %178 : !llvm.ptr -> i64
func.return %603 : i64
}
func.func @main() -> i32 {
%604 = llvm.mlir.addressof @str_0 : !llvm.ptr
%606 = arith.constant 5000 : i32
%607 = arith.constant 1000000000 : i32
%608 = arith.extsi %606 : i32 to i64
%609 = arith.extsi %607 : i32 to i64
%605 = func.call @solve_S_mod(%608, %609) : (i64, i64) -> i64
%610 = llvm.call @printf(%604, %605) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%611 = arith.constant 0 : i32
func.return %611 : i32
}
}