Problem 511
Nice sequences — Seq(1234567898765,4321) mod 1e9 via cyclic convolution.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | ? |
|---|
| Space complexity | O(n^2) | ? |
|---|
| Approach | Flow solution | Not curated |
|---|
| Verdict | Unknown |
|---|
Flow source
# Project Euler 511
# Nice sequences — Seq(1234567898765,4321) mod 1e9 via cyclic convolution.
const MOD: i64 = 1000000000
const K: i64 = 4321
const TARGET_N: i64 = 1234567898765
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function egcd(a0: i64, b0: i64, x: ptr<i64>, y: ptr<i64>) -> i64 {
let mut a: i64 = a0
let mut b: i64 = b0
let mut x1: i64 = 1
let mut y1: i64 = 0
let mut x2: i64 = 0
let mut y2: i64 = 1
while b != 0 {
let q: i64 = a / b
let tx: i64 = x1 - q * x2
let ty: i64 = y1 - q * y2
x1 = x2
y1 = y2
x2 = tx
y2 = ty
let ta: i64 = a
a = b
b = ta % b
}
x[0] = x1
y[0] = y1
return a
}
function factorize(n0: i64, primes: ptr<i64>, exps: ptr<i64>) -> i64 {
let mut n: i64 = n0
let mut nf: i64 = 0
let mut cnt: i64 = 0
while n % 2 == 0 {
n = n / 2
cnt = cnt + 1
}
if cnt > 0 {
primes[nf] = 2
exps[nf] = cnt
nf = nf + 1
}
cnt = 0
while n % 3 == 0 {
n = n / 3
cnt = cnt + 1
}
if cnt > 0 {
primes[nf] = 3
exps[nf] = cnt
nf = nf + 1
}
let mut f: i64 = 5
let mut step: i64 = 2
while f * f <= n {
cnt = 0
while n % f == 0 {
n = n / f
cnt = cnt + 1
}
if cnt > 0 {
primes[nf] = f
exps[nf] = cnt
nf = nf + 1
}
f = f + step
step = 6 - step
}
if n > 1 {
primes[nf] = n
exps[nf] = 1
nf = nf + 1
}
return nf
}
function div_rec(i: i64, nf: i64, cur: i64, primes: ptr<i64>, exps: ptr<i64>, counts: ptr<i64>) -> void {
if i == nf {
let r: i64 = cur % K
counts[r] = counts[r] + 1
return
}
let mut v: i64 = cur
let mut e: i64 = 0
while e <= exps[i] {
div_rec(i + 1, nf, v, primes, exps, counts)
v = v * primes[i]
e = e + 1
}
}
function divisor_counts(n0: i64, counts: ptr<i64>) -> void {
let primes: ptr<i64> = calloc(32, 8)
let exps: ptr<i64> = calloc(32, 8)
if primes == null || exps == null { return }
let nf: i64 = factorize(n0, primes, exps)
div_rec(0, nf, 1, primes, exps, counts)
free(primes)
free(exps)
}
function mul_cyclic(a: ptr<i64>, b: ptr<i64>, out: ptr<i64>) -> void {
let mut i: i64 = 0
while i < K {
out[i] = 0
i = i + 1
}
i = 0
while i < K {
if a[i] != 0 {
let mut j: i64 = 0
while j < K {
if b[j] != 0 {
let idx: i64 = (i + j) % K
out[idx] = (out[idx] + a[i] * b[j]) % MOD
}
j = j + 1
}
}
i = i + 1
}
}
function copy_arr(src: ptr<i64>, dst: ptr<i64>) -> void {
let mut i: i64 = 0
while i < K {
dst[i] = src[i]
i = i + 1
}
}
function pow_cyclic(base: ptr<i64>, exp0: i64, res: ptr<i64>, tmp: ptr<i64>, tmp2: ptr<i64>) -> void {
let mut i: i64 = 0
while i < K {
res[i] = 0
i = i + 1
}
res[0] = 1
copy_arr(base, tmp)
let mut e: i64 = exp0
while e > 0 {
if (e & 1) != 0 {
mul_cyclic(res, tmp, tmp2)
copy_arr(tmp2, res)
}
mul_cyclic(tmp, tmp, tmp2)
copy_arr(tmp2, tmp)
e = e >> 1
}
}
function main() -> i32 {
let counts: ptr<i64> = calloc(K, 8)
let base: ptr<i64> = calloc(K, 8)
let res: ptr<i64> = calloc(K, 8)
let tmp: ptr<i64> = calloc(K, 8)
let tmp2: ptr<i64> = calloc(K, 8)
if counts == null || base == null || res == null || tmp == null || tmp2 == null { return 1 }
divisor_counts(TARGET_N, counts)
let mut i: i64 = 0
while i < K {
base[i] = counts[i] % MOD
i = i + 1
}
pow_cyclic(base, TARGET_N, res, tmp, tmp2)
let need: i64 = ((-TARGET_N) % K + K) % K
printf("%lld\n", res[need] % MOD)
free(counts); free(base); free(res); free(tmp); free(tmp2)
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 egcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* x, int64_t* y);
int64_t factorize_i64_ptr_i64_ptr_i64(int64_t n0, int64_t* primes, int64_t* exps);
void div_rec_i64_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t i, int64_t nf, int64_t cur, int64_t* primes, int64_t* exps, int64_t* counts);
void divisor_counts_i64_ptr_i64(int64_t n0, int64_t* counts);
void mul_cyclic_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out);
void copy_arr_ptr_i64_ptr_i64(int64_t* src, int64_t* dst);
void pow_cyclic_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t* base, int64_t exp0, int64_t* res, int64_t* tmp, int64_t* tmp2);
int32_t main(void);
static const int64_t MOD = 1000000000;
static const int64_t K = 4321;
static const int64_t TARGET_N = 1234567898765;
int64_t egcd_i64_i64_ptr_i64_ptr_i64(int64_t a0, int64_t b0, int64_t* x, int64_t* y) {
int64_t a = a0;
int64_t b = b0;
int64_t x1 = 1;
int64_t y1 = 0;
int64_t x2 = 0;
int64_t y2 = 1;
while (b != 0) {
int64_t q = FLOW_CHECKED_DIV((a), (b));
int64_t tx = (x1 - (q * x2));
int64_t ty = (y1 - (q * y2));
x1 = x2;
y1 = y2;
x2 = tx;
y2 = ty;
int64_t ta = a;
a = b;
b = FLOW_CHECKED_MOD((ta), (b));
}
x[0] = x1;
y[0] = y1;
return a;
}
int64_t factorize_i64_ptr_i64_ptr_i64(int64_t n0, int64_t* primes, int64_t* exps) {
int64_t n = n0;
int64_t nf = 0;
int64_t cnt = 0;
while (FLOW_CHECKED_MOD((n), (2)) == 0) {
n = FLOW_CHECKED_DIV((n), (2));
cnt = (cnt + 1);
}
if (cnt > 0) {
primes[nf] = 2;
exps[nf] = cnt;
nf = (nf + 1);
}
cnt = 0;
while (FLOW_CHECKED_MOD((n), (3)) == 0) {
n = FLOW_CHECKED_DIV((n), (3));
cnt = (cnt + 1);
}
if (cnt > 0) {
primes[nf] = 3;
exps[nf] = cnt;
nf = (nf + 1);
}
int64_t f = 5;
int64_t step = 2;
while ((f * f) <= n) {
cnt = 0;
while (FLOW_CHECKED_MOD((n), (f)) == 0) {
n = FLOW_CHECKED_DIV((n), (f));
cnt = (cnt + 1);
}
if (cnt > 0) {
primes[nf] = f;
exps[nf] = cnt;
nf = (nf + 1);
}
f = (f + step);
step = (6 - step);
}
if (n > 1) {
primes[nf] = n;
exps[nf] = 1;
nf = (nf + 1);
}
return nf;
}
void div_rec_i64_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t i, int64_t nf, int64_t cur, int64_t* primes, int64_t* exps, int64_t* counts) {
if (i == nf) {
int64_t r = FLOW_CHECKED_MOD((cur), (K));
counts[r] = (counts[r] + 1);
return;
}
int64_t v = cur;
int64_t e = 0;
while (e <= exps[i]) {
div_rec_i64_i64_i64_ptr_i64_ptr_i64_ptr_i64((i + 1), nf, v, primes, exps, counts);
v = (v * primes[i]);
e = (e + 1);
}
}
void divisor_counts_i64_ptr_i64(int64_t n0, int64_t* counts) {
int64_t* primes = (int64_t*)(calloc(32, 8));
int64_t* exps = (int64_t*)(calloc(32, 8));
if ((primes == NULL || exps == NULL)) {
return;
}
int64_t nf = factorize_i64_ptr_i64_ptr_i64(n0, primes, exps);
div_rec_i64_i64_i64_ptr_i64_ptr_i64_ptr_i64(0, nf, 1, primes, exps, counts);
free(primes);
free(exps);
}
void mul_cyclic_ptr_i64_ptr_i64_ptr_i64(int64_t* a, int64_t* b, int64_t* out) {
int64_t i = 0;
while (i < K) {
out[i] = 0;
i = (i + 1);
}
i = 0;
while (i < K) {
if (a[i] != 0) {
int64_t j = 0;
while (j < K) {
if (b[j] != 0) {
int64_t idx = FLOW_CHECKED_MOD(((i + j)), (K));
out[idx] = FLOW_CHECKED_MOD(((out[idx] + (a[i] * b[j]))), (MOD));
}
j = (j + 1);
}
}
i = (i + 1);
}
}
void copy_arr_ptr_i64_ptr_i64(int64_t* src, int64_t* dst) {
int64_t i = 0;
while (i < K) {
dst[i] = src[i];
i = (i + 1);
}
}
void pow_cyclic_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i64(int64_t* base, int64_t exp0, int64_t* res, int64_t* tmp, int64_t* tmp2) {
int64_t i = 0;
while (i < K) {
res[i] = 0;
i = (i + 1);
}
res[0] = 1;
copy_arr_ptr_i64_ptr_i64(base, tmp);
int64_t e = exp0;
while (e > 0) {
if ((e & 1) != 0) {
mul_cyclic_ptr_i64_ptr_i64_ptr_i64(res, tmp, tmp2);
copy_arr_ptr_i64_ptr_i64(tmp2, res);
}
mul_cyclic_ptr_i64_ptr_i64_ptr_i64(tmp, tmp, tmp2);
copy_arr_ptr_i64_ptr_i64(tmp2, tmp);
e = FLOW_CHECKED_SHR((e), (1));
}
}
int32_t main(void) {
int64_t* counts = (int64_t*)(calloc(K, 8));
int64_t* base = (int64_t*)(calloc(K, 8));
int64_t* res = (int64_t*)(calloc(K, 8));
int64_t* tmp = (int64_t*)(calloc(K, 8));
int64_t* tmp2 = (int64_t*)(calloc(K, 8));
if (((((counts == NULL || base == NULL) || res == NULL) || tmp == NULL) || tmp2 == NULL)) {
return 1;
}
divisor_counts_i64_ptr_i64(TARGET_N, counts);
int64_t i = 0;
while (i < K) {
base[i] = FLOW_CHECKED_MOD((counts[i]), (MOD));
i = (i + 1);
}
pow_cyclic_ptr_i64_i64_ptr_i64_ptr_i64_ptr_i64(base, TARGET_N, res, tmp, tmp2);
int64_t need = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((-TARGET_N)), (K)) + K)), (K));
printf("%lld\n", FLOW_CHECKED_MOD((res[need]), (MOD)));
free(counts);
free(base);
free(res);
free(tmp);
free(tmp2);
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>
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000000 : i64) : i64
// Constant: K
llvm.mlir.global internal constant @K(4321 : i64) : i64
// Constant: TARGET_N
llvm.mlir.global internal constant @TARGET_N(1234567898765 : i64) : i64
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @egcd(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> 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 = arith.constant 1 : i32
%5 = arith.extsi %4 : i32 to i64
%6 = llvm.mlir.constant(1 : i64) : i64
%7 = llvm.alloca %6 x i64 : (i64) -> !llvm.ptr
llvm.store %5, %7 : i64, !llvm.ptr
%8 = arith.constant 0 : i32
%9 = arith.extsi %8 : i32 to i64
%10 = llvm.mlir.constant(1 : i64) : i64
%11 = llvm.alloca %10 x i64 : (i64) -> !llvm.ptr
llvm.store %9, %11 : i64, !llvm.ptr
%12 = arith.constant 0 : i32
%13 = arith.extsi %12 : i32 to i64
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
llvm.store %13, %15 : i64, !llvm.ptr
%16 = arith.constant 1 : i32
%17 = arith.extsi %16 : i32 to i64
%18 = llvm.mlir.constant(1 : i64) : i64
%19 = llvm.alloca %18 x i64 : (i64) -> !llvm.ptr
llvm.store %17, %19 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%20 = llvm.load %3 : !llvm.ptr -> i64
%21 = arith.constant 0 : i32
%23 = arith.extsi %21 : i32 to i64
%22 = arith.cmpi ne, %20, %23 : i64
cf.cond_br %22, ^bb1, ^bb2
^bb1:
%24 = llvm.load %1 : !llvm.ptr -> i64
%25 = llvm.load %3 : !llvm.ptr -> i64
%26 = arith.divsi %24, %25 : i64
%27 = llvm.load %7 : !llvm.ptr -> i64
%28 = llvm.load %15 : !llvm.ptr -> i64
%29 = arith.muli %26, %28 : i64
%30 = arith.subi %27, %29 : i64
%31 = llvm.load %11 : !llvm.ptr -> i64
%32 = llvm.load %19 : !llvm.ptr -> i64
%33 = arith.muli %26, %32 : i64
%34 = arith.subi %31, %33 : i64
%35 = llvm.load %15 : !llvm.ptr -> i64
llvm.store %35, %7 : i64, !llvm.ptr
%36 = llvm.load %19 : !llvm.ptr -> i64
llvm.store %36, %11 : i64, !llvm.ptr
llvm.store %30, %15 : i64, !llvm.ptr
llvm.store %34, %19 : i64, !llvm.ptr
%37 = llvm.load %1 : !llvm.ptr -> i64
%38 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %38, %1 : i64, !llvm.ptr
%39 = llvm.load %3 : !llvm.ptr -> i64
%40 = arith.remsi %37, %39 : i64
llvm.store %40, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%41 = llvm.load %7 : !llvm.ptr -> i64
%42 = arith.constant 0 : i32
%43 = arith.extsi %42 : i32 to i64
%44 = llvm.getelementptr %arg2[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %41, %44 : i64, !llvm.ptr
%45 = llvm.load %11 : !llvm.ptr -> i64
%46 = arith.constant 0 : i32
%47 = arith.extsi %46 : i32 to i64
%48 = llvm.getelementptr %arg3[%47] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %45, %48 : i64, !llvm.ptr
%49 = llvm.load %1 : !llvm.ptr -> i64
func.return %49 : i64
}
func.func @factorize(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
%50 = llvm.mlir.constant(1 : i64) : i64
%51 = llvm.alloca %50 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %51 : i64, !llvm.ptr
%52 = arith.constant 0 : i32
%53 = arith.extsi %52 : i32 to i64
%54 = llvm.mlir.constant(1 : i64) : i64
%55 = llvm.alloca %54 x i64 : (i64) -> !llvm.ptr
llvm.store %53, %55 : i64, !llvm.ptr
%56 = arith.constant 0 : i32
%57 = arith.extsi %56 : i32 to i64
%58 = llvm.mlir.constant(1 : i64) : i64
%59 = llvm.alloca %58 x i64 : (i64) -> !llvm.ptr
llvm.store %57, %59 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%60 = llvm.load %51 : !llvm.ptr -> i64
%61 = arith.constant 2 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.remsi %60, %63 : i64
%64 = arith.constant 0 : i32
%66 = arith.extsi %64 : i32 to i64
%65 = arith.cmpi eq, %62, %66 : i64
cf.cond_br %65, ^bb4, ^bb5
^bb4:
%67 = llvm.load %51 : !llvm.ptr -> i64
%68 = arith.constant 2 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.divsi %67, %70 : i64
llvm.store %69, %51 : i64, !llvm.ptr
%71 = llvm.load %59 : !llvm.ptr -> i64
%72 = arith.constant 1 : i32
%74 = arith.extsi %72 : i32 to i64
%73 = arith.addi %71, %74 : i64
llvm.store %73, %59 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%75 = llvm.load %59 : !llvm.ptr -> i64
%76 = arith.constant 0 : i32
%78 = arith.extsi %76 : i32 to i64
%77 = arith.cmpi sgt, %75, %78 : i64
cf.cond_br %77, ^bb6, ^bb7
^bb6:
%79 = arith.constant 2 : i32
%80 = llvm.load %55 : !llvm.ptr -> i64
%81 = arith.extsi %79 : i32 to i64
%82 = llvm.getelementptr %arg1[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %81, %82 : i64, !llvm.ptr
%83 = llvm.load %59 : !llvm.ptr -> i64
%84 = llvm.load %55 : !llvm.ptr -> i64
%85 = llvm.getelementptr %arg2[%84] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %83, %85 : i64, !llvm.ptr
%86 = llvm.load %55 : !llvm.ptr -> i64
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.addi %86, %89 : i64
llvm.store %88, %55 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
llvm.store %91, %59 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%92 = llvm.load %51 : !llvm.ptr -> i64
%93 = arith.constant 3 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.remsi %92, %95 : i64
%96 = arith.constant 0 : i32
%98 = arith.extsi %96 : i32 to i64
%97 = arith.cmpi eq, %94, %98 : i64
cf.cond_br %97, ^bb10, ^bb11
^bb10:
%99 = llvm.load %51 : !llvm.ptr -> i64
%100 = arith.constant 3 : i32
%102 = arith.extsi %100 : i32 to i64
%101 = arith.divsi %99, %102 : i64
llvm.store %101, %51 : i64, !llvm.ptr
%103 = llvm.load %59 : !llvm.ptr -> i64
%104 = arith.constant 1 : i32
%106 = arith.extsi %104 : i32 to i64
%105 = arith.addi %103, %106 : i64
llvm.store %105, %59 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%107 = llvm.load %59 : !llvm.ptr -> i64
%108 = arith.constant 0 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.cmpi sgt, %107, %110 : i64
cf.cond_br %109, ^bb12, ^bb13
^bb12:
%111 = arith.constant 3 : i32
%112 = llvm.load %55 : !llvm.ptr -> i64
%113 = arith.extsi %111 : i32 to i64
%114 = llvm.getelementptr %arg1[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %113, %114 : i64, !llvm.ptr
%115 = llvm.load %59 : !llvm.ptr -> i64
%116 = llvm.load %55 : !llvm.ptr -> i64
%117 = llvm.getelementptr %arg2[%116] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %115, %117 : i64, !llvm.ptr
%118 = llvm.load %55 : !llvm.ptr -> i64
%119 = arith.constant 1 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.addi %118, %121 : i64
llvm.store %120, %55 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%122 = arith.constant 5 : i32
%123 = arith.extsi %122 : i32 to i64
%124 = llvm.mlir.constant(1 : i64) : i64
%125 = llvm.alloca %124 x i64 : (i64) -> !llvm.ptr
llvm.store %123, %125 : i64, !llvm.ptr
%126 = arith.constant 2 : 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
cf.br ^bb15
^bb15:
%130 = llvm.load %125 : !llvm.ptr -> i64
%131 = llvm.load %125 : !llvm.ptr -> i64
%132 = arith.muli %130, %131 : i64
%133 = llvm.load %51 : !llvm.ptr -> i64
%134 = arith.cmpi sle, %132, %133 : i64
cf.cond_br %134, ^bb16, ^bb17
^bb16:
%135 = arith.constant 0 : i32
%136 = arith.extsi %135 : i32 to i64
llvm.store %136, %59 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%137 = llvm.load %51 : !llvm.ptr -> i64
%138 = llvm.load %125 : !llvm.ptr -> i64
%139 = arith.remsi %137, %138 : i64
%140 = arith.constant 0 : i32
%142 = arith.extsi %140 : i32 to i64
%141 = arith.cmpi eq, %139, %142 : i64
cf.cond_br %141, ^bb19, ^bb20
^bb19:
%143 = llvm.load %51 : !llvm.ptr -> i64
%144 = llvm.load %125 : !llvm.ptr -> i64
%145 = arith.divsi %143, %144 : i64
llvm.store %145, %51 : i64, !llvm.ptr
%146 = llvm.load %59 : !llvm.ptr -> i64
%147 = arith.constant 1 : i32
%149 = arith.extsi %147 : i32 to i64
%148 = arith.addi %146, %149 : i64
llvm.store %148, %59 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
%150 = llvm.load %59 : !llvm.ptr -> i64
%151 = arith.constant 0 : i32
%153 = arith.extsi %151 : i32 to i64
%152 = arith.cmpi sgt, %150, %153 : i64
cf.cond_br %152, ^bb21, ^bb22
^bb21:
%154 = llvm.load %125 : !llvm.ptr -> i64
%155 = llvm.load %55 : !llvm.ptr -> i64
%156 = llvm.getelementptr %arg1[%155] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %154, %156 : i64, !llvm.ptr
%157 = llvm.load %59 : !llvm.ptr -> i64
%158 = llvm.load %55 : !llvm.ptr -> i64
%159 = llvm.getelementptr %arg2[%158] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %157, %159 : i64, !llvm.ptr
%160 = llvm.load %55 : !llvm.ptr -> i64
%161 = arith.constant 1 : i32
%163 = arith.extsi %161 : i32 to i64
%162 = arith.addi %160, %163 : i64
llvm.store %162, %55 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%164 = llvm.load %125 : !llvm.ptr -> i64
%165 = llvm.load %129 : !llvm.ptr -> i64
%166 = arith.addi %164, %165 : i64
llvm.store %166, %125 : i64, !llvm.ptr
%167 = arith.constant 6 : i32
%168 = llvm.load %129 : !llvm.ptr -> i64
%170 = arith.extsi %167 : i32 to i64
%169 = arith.subi %170, %168 : i64
llvm.store %169, %129 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%171 = llvm.load %51 : !llvm.ptr -> i64
%172 = arith.constant 1 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.cmpi sgt, %171, %174 : i64
cf.cond_br %173, ^bb24, ^bb25
^bb24:
%175 = llvm.load %51 : !llvm.ptr -> i64
%176 = llvm.load %55 : !llvm.ptr -> i64
%177 = llvm.getelementptr %arg1[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %175, %177 : i64, !llvm.ptr
%178 = arith.constant 1 : i32
%179 = llvm.load %55 : !llvm.ptr -> i64
%180 = arith.extsi %178 : i32 to i64
%181 = llvm.getelementptr %arg2[%179] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %180, %181 : i64, !llvm.ptr
%182 = llvm.load %55 : !llvm.ptr -> i64
%183 = arith.constant 1 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.addi %182, %185 : i64
llvm.store %184, %55 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%186 = llvm.load %55 : !llvm.ptr -> i64
func.return %186 : i64
}
func.func @div_rec(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr) -> () {
%187 = arith.cmpi eq, %arg0, %arg1 : i64
cf.cond_br %187, ^bb27, ^bb28
^bb27:
%188 = llvm.mlir.addressof @K : !llvm.ptr
%189 = llvm.load %188 : !llvm.ptr -> i64
%190 = arith.remsi %arg2, %189 : i64
%192 = llvm.getelementptr %arg5[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%191 = llvm.load %192 : !llvm.ptr -> i64
%193 = arith.constant 1 : i32
%195 = arith.extsi %193 : i32 to i64
%194 = arith.addi %191, %195 : i64
%196 = llvm.getelementptr %arg5[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %194, %196 : i64, !llvm.ptr
func.return
^bb28:
cf.br ^bb29
^bb29:
%197 = llvm.mlir.constant(1 : i64) : i64
%198 = llvm.alloca %197 x i64 : (i64) -> !llvm.ptr
llvm.store %arg2, %198 : i64, !llvm.ptr
%199 = arith.constant 0 : i32
%200 = arith.extsi %199 : i32 to i64
%201 = llvm.mlir.constant(1 : i64) : i64
%202 = llvm.alloca %201 x i64 : (i64) -> !llvm.ptr
llvm.store %200, %202 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%203 = llvm.load %202 : !llvm.ptr -> i64
%205 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%204 = llvm.load %205 : !llvm.ptr -> i64
%206 = arith.cmpi sle, %203, %204 : i64
cf.cond_br %206, ^bb31, ^bb32
^bb31:
%208 = arith.constant 1 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.addi %arg0, %210 : i64
%211 = llvm.load %198 : !llvm.ptr -> i64
func.call @div_rec(%209, %arg1, %211, %arg3, %arg4, %arg5) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%212 = llvm.load %198 : !llvm.ptr -> i64
%214 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%213 = llvm.load %214 : !llvm.ptr -> i64
%215 = arith.muli %212, %213 : i64
llvm.store %215, %198 : i64, !llvm.ptr
%216 = llvm.load %202 : !llvm.ptr -> i64
%217 = arith.constant 1 : i32
%219 = arith.extsi %217 : i32 to i64
%218 = arith.addi %216, %219 : i64
llvm.store %218, %202 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
func.return
}
func.func @divisor_counts(%arg0: i64, %arg1: !llvm.ptr) -> () {
%221 = arith.constant 32 : i32
%222 = arith.constant 8 : i32
%223 = arith.extsi %221 : i32 to i64
%224 = arith.extsi %222 : i32 to i64
%220 = func.call @calloc(%223, %224) : (i64, i64) -> !llvm.ptr
%226 = arith.constant 32 : i32
%227 = arith.constant 8 : i32
%228 = arith.extsi %226 : i32 to i64
%229 = arith.extsi %227 : i32 to i64
%225 = func.call @calloc(%228, %229) : (i64, i64) -> !llvm.ptr
%230 = llvm.mlir.zero : !llvm.ptr
%231 = llvm.icmp "eq" %220, %230 : !llvm.ptr
%232 = scf.if %231 -> (i1) {
%233 = arith.constant true
scf.yield %233 : i1
} else {
%234 = llvm.mlir.zero : !llvm.ptr
%235 = llvm.icmp "eq" %225, %234 : !llvm.ptr
scf.yield %235 : i1
}
cf.cond_br %232, ^bb33, ^bb34
^bb33:
func.return
^bb34:
cf.br ^bb35
^bb35:
%236 = func.call @factorize(%arg0, %220, %225) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%238 = arith.constant 0 : i32
%239 = arith.constant 1 : i32
%240 = arith.extsi %238 : i32 to i64
%241 = arith.extsi %239 : i32 to i64
func.call @div_rec(%240, %236, %241, %220, %225, %arg1) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @free(%220) : (!llvm.ptr) -> ()
func.call @free(%225) : (!llvm.ptr) -> ()
func.return
}
func.func @mul_cyclic(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> () {
%244 = arith.constant 0 : i32
%245 = arith.extsi %244 : i32 to i64
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.alloca %246 x i64 : (i64) -> !llvm.ptr
llvm.store %245, %247 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%248 = llvm.load %247 : !llvm.ptr -> i64
%249 = llvm.mlir.addressof @K : !llvm.ptr
%250 = llvm.load %249 : !llvm.ptr -> i64
%251 = arith.cmpi slt, %248, %250 : i64
cf.cond_br %251, ^bb37, ^bb38
^bb37:
%252 = arith.constant 0 : i32
%253 = llvm.load %247 : !llvm.ptr -> i64
%254 = arith.extsi %252 : i32 to i64
%255 = llvm.getelementptr %arg2[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %254, %255 : i64, !llvm.ptr
%256 = llvm.load %247 : !llvm.ptr -> i64
%257 = arith.constant 1 : i32
%259 = arith.extsi %257 : i32 to i64
%258 = arith.addi %256, %259 : i64
llvm.store %258, %247 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%260 = arith.constant 0 : i32
%261 = arith.extsi %260 : i32 to i64
llvm.store %261, %247 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%262 = llvm.load %247 : !llvm.ptr -> i64
%263 = llvm.mlir.addressof @K : !llvm.ptr
%264 = llvm.load %263 : !llvm.ptr -> i64
%265 = arith.cmpi slt, %262, %264 : i64
cf.cond_br %265, ^bb40, ^bb41
^bb40:
%267 = llvm.load %247 : !llvm.ptr -> i64
%268 = llvm.getelementptr %arg0[%267] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%266 = llvm.load %268 : !llvm.ptr -> i64
%269 = arith.constant 0 : i32
%271 = arith.extsi %269 : i32 to i64
%270 = arith.cmpi ne, %266, %271 : i64
cf.cond_br %270, ^bb42, ^bb43
^bb42:
%272 = arith.constant 0 : i32
%273 = arith.extsi %272 : i32 to i64
%274 = llvm.mlir.constant(1 : i64) : i64
%275 = llvm.alloca %274 x i64 : (i64) -> !llvm.ptr
llvm.store %273, %275 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%276 = llvm.load %275 : !llvm.ptr -> i64
%277 = llvm.mlir.addressof @K : !llvm.ptr
%278 = llvm.load %277 : !llvm.ptr -> i64
%279 = arith.cmpi slt, %276, %278 : i64
cf.cond_br %279, ^bb46, ^bb47
^bb46:
%281 = llvm.load %275 : !llvm.ptr -> i64
%282 = llvm.getelementptr %arg1[%281] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%280 = llvm.load %282 : !llvm.ptr -> i64
%283 = arith.constant 0 : i32
%285 = arith.extsi %283 : i32 to i64
%284 = arith.cmpi ne, %280, %285 : i64
cf.cond_br %284, ^bb48, ^bb49
^bb48:
%286 = llvm.load %247 : !llvm.ptr -> i64
%287 = llvm.load %275 : !llvm.ptr -> i64
%288 = arith.addi %286, %287 : i64
%289 = llvm.mlir.addressof @K : !llvm.ptr
%290 = llvm.load %289 : !llvm.ptr -> i64
%291 = arith.remsi %288, %290 : i64
%293 = llvm.getelementptr %arg2[%291] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%292 = llvm.load %293 : !llvm.ptr -> i64
%295 = llvm.load %247 : !llvm.ptr -> i64
%296 = llvm.getelementptr %arg0[%295] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%294 = llvm.load %296 : !llvm.ptr -> i64
%298 = llvm.load %275 : !llvm.ptr -> i64
%299 = llvm.getelementptr %arg1[%298] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%297 = llvm.load %299 : !llvm.ptr -> i64
%300 = arith.muli %294, %297 : i64
%301 = arith.addi %292, %300 : i64
%302 = llvm.mlir.addressof @MOD : !llvm.ptr
%303 = llvm.load %302 : !llvm.ptr -> i64
%304 = arith.remsi %301, %303 : i64
%305 = llvm.getelementptr %arg2[%291] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %304, %305 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%306 = llvm.load %275 : !llvm.ptr -> i64
%307 = arith.constant 1 : i32
%309 = arith.extsi %307 : i32 to i64
%308 = arith.addi %306, %309 : i64
llvm.store %308, %275 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%310 = llvm.load %247 : !llvm.ptr -> i64
%311 = arith.constant 1 : i32
%313 = arith.extsi %311 : i32 to i64
%312 = arith.addi %310, %313 : i64
llvm.store %312, %247 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
func.return
}
func.func @copy_arr(%arg0: !llvm.ptr, %arg1: !llvm.ptr) -> () {
%314 = arith.constant 0 : i32
%315 = arith.extsi %314 : i32 to i64
%316 = llvm.mlir.constant(1 : i64) : i64
%317 = llvm.alloca %316 x i64 : (i64) -> !llvm.ptr
llvm.store %315, %317 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%318 = llvm.load %317 : !llvm.ptr -> i64
%319 = llvm.mlir.addressof @K : !llvm.ptr
%320 = llvm.load %319 : !llvm.ptr -> i64
%321 = arith.cmpi slt, %318, %320 : i64
cf.cond_br %321, ^bb52, ^bb53
^bb52:
%323 = llvm.load %317 : !llvm.ptr -> i64
%324 = llvm.getelementptr %arg0[%323] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%322 = llvm.load %324 : !llvm.ptr -> i64
%325 = llvm.load %317 : !llvm.ptr -> i64
%326 = llvm.getelementptr %arg1[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %322, %326 : i64, !llvm.ptr
%327 = llvm.load %317 : !llvm.ptr -> i64
%328 = arith.constant 1 : i32
%330 = arith.extsi %328 : i32 to i64
%329 = arith.addi %327, %330 : i64
llvm.store %329, %317 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
func.return
}
func.func @pow_cyclic(%arg0: !llvm.ptr, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> () {
%331 = arith.constant 0 : i32
%332 = arith.extsi %331 : i32 to i64
%333 = llvm.mlir.constant(1 : i64) : i64
%334 = llvm.alloca %333 x i64 : (i64) -> !llvm.ptr
llvm.store %332, %334 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%335 = llvm.load %334 : !llvm.ptr -> i64
%336 = llvm.mlir.addressof @K : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> i64
%338 = arith.cmpi slt, %335, %337 : i64
cf.cond_br %338, ^bb55, ^bb56
^bb55:
%339 = arith.constant 0 : i32
%340 = llvm.load %334 : !llvm.ptr -> i64
%341 = arith.extsi %339 : i32 to i64
%342 = llvm.getelementptr %arg2[%340] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %341, %342 : i64, !llvm.ptr
%343 = llvm.load %334 : !llvm.ptr -> i64
%344 = arith.constant 1 : i32
%346 = arith.extsi %344 : i32 to i64
%345 = arith.addi %343, %346 : i64
llvm.store %345, %334 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%347 = arith.constant 1 : i32
%348 = arith.constant 0 : i32
%349 = arith.extsi %347 : i32 to i64
%350 = arith.extsi %348 : i32 to i64
%351 = llvm.getelementptr %arg2[%350] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %349, %351 : i64, !llvm.ptr
func.call @copy_arr(%arg0, %arg3) : (!llvm.ptr, !llvm.ptr) -> ()
%353 = llvm.mlir.constant(1 : i64) : i64
%354 = llvm.alloca %353 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %354 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%355 = llvm.load %354 : !llvm.ptr -> i64
%356 = arith.constant 0 : i32
%358 = arith.extsi %356 : i32 to i64
%357 = arith.cmpi sgt, %355, %358 : i64
cf.cond_br %357, ^bb58, ^bb59
^bb58:
%359 = llvm.load %354 : !llvm.ptr -> i64
%360 = arith.constant 1 : i32
%362 = arith.extsi %360 : i32 to i64
%361 = arith.andi %359, %362 : i64
%363 = arith.constant 0 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.cmpi ne, %361, %365 : i64
cf.cond_br %364, ^bb60, ^bb61
^bb60:
func.call @mul_cyclic(%arg2, %arg3, %arg4) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @copy_arr(%arg4, %arg2) : (!llvm.ptr, !llvm.ptr) -> ()
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
func.call @mul_cyclic(%arg3, %arg3, %arg4) : (!llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
func.call @copy_arr(%arg4, %arg3) : (!llvm.ptr, !llvm.ptr) -> ()
%370 = llvm.load %354 : !llvm.ptr -> i64
%371 = arith.constant 1 : i32
%373 = arith.extsi %371 : i32 to i64
%372 = arith.shrsi %370, %373 : i64
llvm.store %372, %354 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
func.return
}
func.func @main() -> i32 {
%375 = llvm.mlir.addressof @K : !llvm.ptr
%376 = llvm.load %375 : !llvm.ptr -> i64
%377 = arith.constant 8 : i32
%378 = arith.extsi %377 : i32 to i64
%374 = func.call @calloc(%376, %378) : (i64, i64) -> !llvm.ptr
%380 = llvm.mlir.addressof @K : !llvm.ptr
%381 = llvm.load %380 : !llvm.ptr -> i64
%382 = arith.constant 8 : i32
%383 = arith.extsi %382 : i32 to i64
%379 = func.call @calloc(%381, %383) : (i64, i64) -> !llvm.ptr
%385 = llvm.mlir.addressof @K : !llvm.ptr
%386 = llvm.load %385 : !llvm.ptr -> i64
%387 = arith.constant 8 : i32
%388 = arith.extsi %387 : i32 to i64
%384 = func.call @calloc(%386, %388) : (i64, i64) -> !llvm.ptr
%390 = llvm.mlir.addressof @K : !llvm.ptr
%391 = llvm.load %390 : !llvm.ptr -> i64
%392 = arith.constant 8 : i32
%393 = arith.extsi %392 : i32 to i64
%389 = func.call @calloc(%391, %393) : (i64, i64) -> !llvm.ptr
%395 = llvm.mlir.addressof @K : !llvm.ptr
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.constant 8 : i32
%398 = arith.extsi %397 : i32 to i64
%394 = func.call @calloc(%396, %398) : (i64, i64) -> !llvm.ptr
%399 = llvm.mlir.zero : !llvm.ptr
%400 = llvm.icmp "eq" %374, %399 : !llvm.ptr
%401 = scf.if %400 -> (i1) {
%402 = arith.constant true
scf.yield %402 : i1
} else {
%403 = llvm.mlir.zero : !llvm.ptr
%404 = llvm.icmp "eq" %379, %403 : !llvm.ptr
scf.yield %404 : i1
}
%405 = scf.if %401 -> (i1) {
%406 = arith.constant true
scf.yield %406 : i1
} else {
%407 = llvm.mlir.zero : !llvm.ptr
%408 = llvm.icmp "eq" %384, %407 : !llvm.ptr
scf.yield %408 : i1
}
%409 = scf.if %405 -> (i1) {
%410 = arith.constant true
scf.yield %410 : i1
} else {
%411 = llvm.mlir.zero : !llvm.ptr
%412 = llvm.icmp "eq" %389, %411 : !llvm.ptr
scf.yield %412 : i1
}
%413 = scf.if %409 -> (i1) {
%414 = arith.constant true
scf.yield %414 : i1
} else {
%415 = llvm.mlir.zero : !llvm.ptr
%416 = llvm.icmp "eq" %394, %415 : !llvm.ptr
scf.yield %416 : i1
}
cf.cond_br %413, ^bb63, ^bb64
^bb63:
%417 = arith.constant 1 : i32
func.return %417 : i32
^bb64:
cf.br ^bb65
^bb65:
%419 = llvm.mlir.addressof @TARGET_N : !llvm.ptr
%420 = llvm.load %419 : !llvm.ptr -> i64
func.call @divisor_counts(%420, %374) : (i64, !llvm.ptr) -> ()
%421 = arith.constant 0 : i32
%422 = arith.extsi %421 : i32 to i64
%423 = llvm.mlir.constant(1 : i64) : i64
%424 = llvm.alloca %423 x i64 : (i64) -> !llvm.ptr
llvm.store %422, %424 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%425 = llvm.load %424 : !llvm.ptr -> i64
%426 = llvm.mlir.addressof @K : !llvm.ptr
%427 = llvm.load %426 : !llvm.ptr -> i64
%428 = arith.cmpi slt, %425, %427 : i64
cf.cond_br %428, ^bb67, ^bb68
^bb67:
%430 = llvm.load %424 : !llvm.ptr -> i64
%431 = llvm.getelementptr %374[%430] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%429 = llvm.load %431 : !llvm.ptr -> i64
%432 = llvm.mlir.addressof @MOD : !llvm.ptr
%433 = llvm.load %432 : !llvm.ptr -> i64
%434 = arith.remsi %429, %433 : i64
%435 = llvm.load %424 : !llvm.ptr -> i64
%436 = llvm.getelementptr %379[%435] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %434, %436 : i64, !llvm.ptr
%437 = llvm.load %424 : !llvm.ptr -> i64
%438 = arith.constant 1 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.addi %437, %440 : i64
llvm.store %439, %424 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%442 = llvm.mlir.addressof @TARGET_N : !llvm.ptr
%443 = llvm.load %442 : !llvm.ptr -> i64
func.call @pow_cyclic(%379, %443, %384, %389, %394) : (!llvm.ptr, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> ()
%444 = llvm.mlir.addressof @TARGET_N : !llvm.ptr
%445 = llvm.load %444 : !llvm.ptr -> i64
%447 = arith.constant 0 : i64
%446 = arith.subi %447, %445 : i64
%448 = llvm.mlir.addressof @K : !llvm.ptr
%449 = llvm.load %448 : !llvm.ptr -> i64
%450 = arith.remsi %446, %449 : i64
%451 = llvm.mlir.addressof @K : !llvm.ptr
%452 = llvm.load %451 : !llvm.ptr -> i64
%453 = arith.addi %450, %452 : i64
%454 = llvm.mlir.addressof @K : !llvm.ptr
%455 = llvm.load %454 : !llvm.ptr -> i64
%456 = arith.remsi %453, %455 : i64
%457 = llvm.mlir.addressof @str_0 : !llvm.ptr
%459 = llvm.getelementptr %384[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%458 = llvm.load %459 : !llvm.ptr -> i64
%460 = llvm.mlir.addressof @MOD : !llvm.ptr
%461 = llvm.load %460 : !llvm.ptr -> i64
%462 = arith.remsi %458, %461 : i64
%463 = llvm.call @printf(%457, %462) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%374) : (!llvm.ptr) -> ()
func.call @free(%379) : (!llvm.ptr) -> ()
func.call @free(%384) : (!llvm.ptr) -> ()
func.call @free(%389) : (!llvm.ptr) -> ()
func.call @free(%394) : (!llvm.ptr) -> ()
%469 = arith.constant 0 : i32
func.return %469 : i32
}
}