← All problems Problem 552
Chinese Leftovers II Track A_n residues mod all primes <= L; sum primes that ever divide some A_n.
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 552
# Chinese Leftovers II
# Track A_n residues mod all primes <= L; sum primes that ever divide some A_n.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function modpow(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut result: i64 = 1
let mut base: i64 = base0 % mod
let mut exp: i64 = exp0
while exp > 0 {
if (exp & 1) != 0 {
result = ((result as i128) * (base as i128) % (mod as i128)) as i64
}
base = ((base as i128) * (base as i128) % (mod as i128)) as i64
exp = exp >> 1
}
return result
}
function compute_S(limit: i64) -> i64 {
let sieve: ptr<i8> = calloc(limit + 1, 1)
if sieve == null { return -1 }
let mut i: i64 = 0
while i <= limit {
sieve[i] = 1
i = i + 1
}
sieve[0] = 0
sieve[1] = 0
i = 2
while i * i <= limit {
if sieve[i] != 0 {
let mut j: i64 = i * i
while j <= limit {
sieve[j] = 0
j = j + i
}
}
i = i + 1
}
let primes: ptr<i64> = calloc(30000, 8)
if primes == null { free(sieve); return -1 }
let mut m: i64 = 0
i = 2
while i <= limit {
if sieve[i] != 0 {
primes[m] = i
m = m + 1
}
i = i + 1
}
free(sieve)
if m <= 1 {
free(primes)
return 0
}
let a_mod: ptr<i64> = calloc(m, 8)
let m_mod: ptr<i64> = calloc(m, 8)
let found: ptr<i8> = calloc(m, 1)
if a_mod == null || m_mod == null || found == null { return -1 }
let mut j: i64 = 0
while j < m {
let q: i64 = primes[j]
a_mod[j] = 1 % q
m_mod[j] = 2 % q
j = j + 1
}
let mut idx: i64 = 1
while idx < m {
let p: i64 = primes[idx]
let inv: i64 = modpow(m_mod[idx], p - 2, p)
let mut t: i64 = ((idx + 1 - a_mod[idx]) % p) * inv % p
if t < 0 { t = t + p }
j = idx + 1
while j < m {
let q: i64 = primes[j]
let a: i64 = (a_mod[j] + m_mod[j] * t % q) % q
a_mod[j] = a
m_mod[j] = m_mod[j] * p % q
if a == 0 {
found[j] = 1
}
j = j + 1
}
idx = idx + 1
}
let mut ans: i64 = 0
j = 0
while j < m {
if found[j] != 0 {
ans = ans + primes[j]
}
j = j + 1
}
free(primes)
free(a_mod)
free(m_mod)
free(found)
return ans
}
function main() -> i32 {
printf("%lld\n", compute_S(300000))
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 modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int64_t compute_S_i64(int64_t limit);
int32_t main(void);
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t result = 1;
int64_t base = FLOW_CHECKED_MOD((base0), (mod));
int64_t exp = exp0;
while (exp > 0) {
if ((exp & 1) != 0) {
result = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(result)) * ((__int128)(base)))), (((__int128)(mod))))));
}
base = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(base)) * ((__int128)(base)))), (((__int128)(mod))))));
exp = FLOW_CHECKED_SHR((exp), (1));
}
return result;
}
int64_t compute_S_i64(int64_t limit) {
int8_t* sieve = (int8_t*)(calloc((limit + 1), 1));
if (sieve == NULL) {
return (-1);
}
int64_t i = 0;
while (i <= limit) {
sieve[i] = 1;
i = (i + 1);
}
sieve[0] = 0;
sieve[1] = 0;
i = 2;
while ((i * i) <= limit) {
if (sieve[i] != 0) {
int64_t j = (i * i);
while (j <= limit) {
sieve[j] = 0;
j = (j + i);
}
}
i = (i + 1);
}
int64_t* primes = (int64_t*)(calloc(30000, 8));
if (primes == NULL) {
free(sieve);
return (-1);
}
int64_t m = 0;
i = 2;
while (i <= limit) {
if (sieve[i] != 0) {
primes[m] = i;
m = (m + 1);
}
i = (i + 1);
}
free(sieve);
if (m <= 1) {
free(primes);
return 0;
}
int64_t* a_mod = (int64_t*)(calloc(m, 8));
int64_t* m_mod = (int64_t*)(calloc(m, 8));
int8_t* found = (int8_t*)(calloc(m, 1));
if (((a_mod == NULL || m_mod == NULL) || found == NULL)) {
return (-1);
}
int64_t j = 0;
while (j < m) {
int64_t q = primes[j];
a_mod[j] = FLOW_CHECKED_MOD((1), (q));
m_mod[j] = FLOW_CHECKED_MOD((2), (q));
j = (j + 1);
}
int64_t idx = 1;
while (idx < m) {
int64_t p = primes[idx];
int64_t inv = modpow_i64_i64_i64(m_mod[idx], (p - 2), p);
int64_t t = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((idx + 1) - a_mod[idx])), (p)) * inv)), (p));
if (t < 0) {
t = (t + p);
}
j = (idx + 1);
while (j < m) {
int64_t q = primes[j];
int64_t a = FLOW_CHECKED_MOD(((a_mod[j] + FLOW_CHECKED_MOD(((m_mod[j] * t)), (q)))), (q));
a_mod[j] = a;
m_mod[j] = FLOW_CHECKED_MOD(((m_mod[j] * p)), (q));
if (a == 0) {
found[j] = 1;
}
j = (j + 1);
}
idx = (idx + 1);
}
int64_t ans = 0;
j = 0;
while (j < m) {
if (found[j] != 0) {
ans = (ans + primes[j]);
}
j = (j + 1);
}
free(primes);
free(a_mod);
free(m_mod);
free(found);
return ans;
}
int32_t main(void) {
printf("%lld\n", compute_S_i64(300000));
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 @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.remsi %arg0, %arg2 : i64
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i64, !llvm.ptr
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi sgt, %9, %12 : i64
cf.cond_br %11, ^bb1, ^bb2
^bb1:
%13 = llvm.load %8 : !llvm.ptr -> i64
%14 = arith.constant 1 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.andi %13, %16 : i64
%17 = arith.constant 0 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.cmpi ne, %15, %19 : i64
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%20 = llvm.load %3 : !llvm.ptr -> i64
%21 = arith.extsi %20 : i64 to i128
%22 = llvm.load %6 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%25 = arith.trunci %21 : i128 to i64
%26 = arith.trunci %23 : i128 to i64
%24 = arith.muli %25, %26 : i64
%27 = arith.extsi %arg2 : i64 to i128
%29 = arith.trunci %27 : i128 to i64
%28 = arith.remsi %24, %29 : i64
llvm.store %28, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%30 = llvm.load %6 : !llvm.ptr -> i64
%31 = arith.extsi %30 : i64 to i128
%32 = llvm.load %6 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%35 = arith.trunci %31 : i128 to i64
%36 = arith.trunci %33 : i128 to i64
%34 = arith.muli %35, %36 : i64
%37 = arith.extsi %arg2 : i64 to i128
%39 = arith.trunci %37 : i128 to i64
%38 = arith.remsi %34, %39 : i64
llvm.store %38, %6 : i64, !llvm.ptr
%40 = llvm.load %8 : !llvm.ptr -> i64
%41 = arith.constant 1 : i32
%43 = arith.extsi %41 : i32 to i64
%42 = arith.shrsi %40, %43 : i64
llvm.store %42, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%44 = llvm.load %3 : !llvm.ptr -> i64
func.return %44 : i64
}
func.func @compute_S(%arg0: i64) -> i64 {
%46 = arith.constant 1 : i32
%48 = arith.extsi %46 : i32 to i64
%47 = arith.addi %arg0, %48 : i64
%49 = arith.constant 1 : i32
%50 = arith.extsi %49 : i32 to i64
%45 = func.call @calloc(%47, %50) : (i64, i64) -> !llvm.ptr
%51 = llvm.mlir.zero : !llvm.ptr
%52 = llvm.icmp "eq" %45, %51 : !llvm.ptr
cf.cond_br %52, ^bb6, ^bb7
^bb6:
%53 = arith.constant 1 : i32
%55 = arith.constant 0 : i32
%54 = arith.subi %55, %53 : i32
%56 = arith.extsi %54 : i32 to i64
func.return %56 : i64
^bb7:
cf.br ^bb8
^bb8:
%57 = arith.constant 0 : i32
%58 = arith.extsi %57 : i32 to i64
%59 = llvm.mlir.constant(1 : i64) : i64
%60 = llvm.alloca %59 x i64 : (i64) -> !llvm.ptr
llvm.store %58, %60 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%61 = llvm.load %60 : !llvm.ptr -> i64
%62 = arith.cmpi sle, %61, %arg0 : i64
cf.cond_br %62, ^bb10, ^bb11
^bb10:
%63 = arith.constant 1 : i32
%64 = llvm.load %60 : !llvm.ptr -> i64
%65 = arith.trunci %63 : i32 to i8
%66 = llvm.getelementptr %45[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %65, %66 : i8, !llvm.ptr
%67 = llvm.load %60 : !llvm.ptr -> i64
%68 = arith.constant 1 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.addi %67, %70 : i64
llvm.store %69, %60 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%71 = arith.constant 0 : i32
%72 = arith.constant 0 : i32
%73 = arith.trunci %71 : i32 to i8
%74 = arith.extsi %72 : i32 to i64
%75 = llvm.getelementptr %45[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %73, %75 : i8, !llvm.ptr
%76 = arith.constant 0 : i32
%77 = arith.constant 1 : i32
%78 = arith.trunci %76 : i32 to i8
%79 = arith.extsi %77 : i32 to i64
%80 = llvm.getelementptr %45[%79] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %78, %80 : i8, !llvm.ptr
%81 = arith.constant 2 : i32
%82 = arith.extsi %81 : i32 to i64
llvm.store %82, %60 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%83 = llvm.load %60 : !llvm.ptr -> i64
%84 = llvm.load %60 : !llvm.ptr -> i64
%85 = arith.muli %83, %84 : i64
%86 = arith.cmpi sle, %85, %arg0 : i64
cf.cond_br %86, ^bb13, ^bb14
^bb13:
%88 = llvm.load %60 : !llvm.ptr -> i64
%89 = llvm.getelementptr %45[%88] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%87 = llvm.load %89 : !llvm.ptr -> i8
%90 = arith.constant 0 : i32
%92 = arith.extsi %87 : i8 to i32
%91 = arith.cmpi ne, %92, %90 : i32
cf.cond_br %91, ^bb15, ^bb16
^bb15:
%93 = llvm.load %60 : !llvm.ptr -> i64
%94 = llvm.load %60 : !llvm.ptr -> i64
%95 = arith.muli %93, %94 : i64
%96 = llvm.mlir.constant(1 : i64) : i64
%97 = llvm.alloca %96 x i64 : (i64) -> !llvm.ptr
llvm.store %95, %97 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%98 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.cmpi sle, %98, %arg0 : i64
cf.cond_br %99, ^bb19, ^bb20
^bb19:
%100 = arith.constant 0 : i32
%101 = llvm.load %97 : !llvm.ptr -> i64
%102 = arith.trunci %100 : i32 to i8
%103 = llvm.getelementptr %45[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %102, %103 : i8, !llvm.ptr
%104 = llvm.load %97 : !llvm.ptr -> i64
%105 = llvm.load %60 : !llvm.ptr -> i64
%106 = arith.addi %104, %105 : i64
llvm.store %106, %97 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%107 = llvm.load %60 : !llvm.ptr -> i64
%108 = arith.constant 1 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.addi %107, %110 : i64
llvm.store %109, %60 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%112 = arith.constant 30000 : i32
%113 = arith.constant 8 : i32
%114 = arith.extsi %112 : i32 to i64
%115 = arith.extsi %113 : i32 to i64
%111 = func.call @calloc(%114, %115) : (i64, i64) -> !llvm.ptr
%116 = llvm.mlir.zero : !llvm.ptr
%117 = llvm.icmp "eq" %111, %116 : !llvm.ptr
cf.cond_br %117, ^bb21, ^bb22
^bb21:
func.call @free(%45) : (!llvm.ptr) -> ()
%119 = arith.constant 1 : i32
%121 = arith.constant 0 : i32
%120 = arith.subi %121, %119 : i32
%122 = arith.extsi %120 : i32 to i64
func.return %122 : i64
^bb22:
cf.br ^bb23
^bb23:
%123 = arith.constant 0 : i32
%124 = arith.extsi %123 : i32 to i64
%125 = llvm.mlir.constant(1 : i64) : i64
%126 = llvm.alloca %125 x i64 : (i64) -> !llvm.ptr
llvm.store %124, %126 : i64, !llvm.ptr
%127 = arith.constant 2 : i32
%128 = arith.extsi %127 : i32 to i64
llvm.store %128, %60 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%129 = llvm.load %60 : !llvm.ptr -> i64
%130 = arith.cmpi sle, %129, %arg0 : i64
cf.cond_br %130, ^bb25, ^bb26
^bb25:
%132 = llvm.load %60 : !llvm.ptr -> i64
%133 = llvm.getelementptr %45[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%131 = llvm.load %133 : !llvm.ptr -> i8
%134 = arith.constant 0 : i32
%136 = arith.extsi %131 : i8 to i32
%135 = arith.cmpi ne, %136, %134 : i32
cf.cond_br %135, ^bb27, ^bb28
^bb27:
%137 = llvm.load %60 : !llvm.ptr -> i64
%138 = llvm.load %126 : !llvm.ptr -> i64
%139 = llvm.getelementptr %111[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %137, %139 : i64, !llvm.ptr
%140 = llvm.load %126 : !llvm.ptr -> i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.addi %140, %143 : i64
llvm.store %142, %126 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%144 = llvm.load %60 : !llvm.ptr -> i64
%145 = arith.constant 1 : i32
%147 = arith.extsi %145 : i32 to i64
%146 = arith.addi %144, %147 : i64
llvm.store %146, %60 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
func.call @free(%45) : (!llvm.ptr) -> ()
%149 = llvm.load %126 : !llvm.ptr -> i64
%150 = arith.constant 1 : i32
%152 = arith.extsi %150 : i32 to i64
%151 = arith.cmpi sle, %149, %152 : i64
cf.cond_br %151, ^bb30, ^bb31
^bb30:
func.call @free(%111) : (!llvm.ptr) -> ()
%154 = arith.constant 0 : i32
%155 = arith.extsi %154 : i32 to i64
func.return %155 : i64
^bb31:
cf.br ^bb32
^bb32:
%157 = llvm.load %126 : !llvm.ptr -> i64
%158 = arith.constant 8 : i32
%159 = arith.extsi %158 : i32 to i64
%156 = func.call @calloc(%157, %159) : (i64, i64) -> !llvm.ptr
%161 = llvm.load %126 : !llvm.ptr -> i64
%162 = arith.constant 8 : i32
%163 = arith.extsi %162 : i32 to i64
%160 = func.call @calloc(%161, %163) : (i64, i64) -> !llvm.ptr
%165 = llvm.load %126 : !llvm.ptr -> i64
%166 = arith.constant 1 : i32
%167 = arith.extsi %166 : i32 to i64
%164 = func.call @calloc(%165, %167) : (i64, i64) -> !llvm.ptr
%168 = llvm.mlir.zero : !llvm.ptr
%169 = llvm.icmp "eq" %156, %168 : !llvm.ptr
%170 = scf.if %169 -> (i1) {
%171 = arith.constant true
scf.yield %171 : i1
} else {
%172 = llvm.mlir.zero : !llvm.ptr
%173 = llvm.icmp "eq" %160, %172 : !llvm.ptr
scf.yield %173 : i1
}
%174 = scf.if %170 -> (i1) {
%175 = arith.constant true
scf.yield %175 : i1
} else {
%176 = llvm.mlir.zero : !llvm.ptr
%177 = llvm.icmp "eq" %164, %176 : !llvm.ptr
scf.yield %177 : i1
}
cf.cond_br %174, ^bb33, ^bb34
^bb33:
%178 = arith.constant 1 : i32
%180 = arith.constant 0 : i32
%179 = arith.subi %180, %178 : i32
%181 = arith.extsi %179 : i32 to i64
func.return %181 : i64
^bb34:
cf.br ^bb35
^bb35:
%182 = arith.constant 0 : i32
%183 = arith.extsi %182 : i32 to i64
%184 = llvm.mlir.constant(1 : i64) : i64
%185 = llvm.alloca %184 x i64 : (i64) -> !llvm.ptr
llvm.store %183, %185 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%186 = llvm.load %185 : !llvm.ptr -> i64
%187 = llvm.load %126 : !llvm.ptr -> i64
%188 = arith.cmpi slt, %186, %187 : i64
cf.cond_br %188, ^bb37, ^bb38
^bb37:
%190 = llvm.load %185 : !llvm.ptr -> i64
%191 = llvm.getelementptr %111[%190] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%189 = llvm.load %191 : !llvm.ptr -> i64
%192 = arith.constant 1 : i32
%194 = arith.extsi %192 : i32 to i64
%193 = arith.remsi %194, %189 : i64
%195 = llvm.load %185 : !llvm.ptr -> i64
%196 = llvm.getelementptr %156[%195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %193, %196 : i64, !llvm.ptr
%197 = arith.constant 2 : i32
%199 = arith.extsi %197 : i32 to i64
%198 = arith.remsi %199, %189 : i64
%200 = llvm.load %185 : !llvm.ptr -> i64
%201 = llvm.getelementptr %160[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %198, %201 : i64, !llvm.ptr
%202 = llvm.load %185 : !llvm.ptr -> i64
%203 = arith.constant 1 : i32
%205 = arith.extsi %203 : i32 to i64
%204 = arith.addi %202, %205 : i64
llvm.store %204, %185 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%206 = arith.constant 1 : i32
%207 = arith.extsi %206 : i32 to i64
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
llvm.store %207, %209 : i64, !llvm.ptr
cf.br ^bb39
^bb39:
%210 = llvm.load %209 : !llvm.ptr -> i64
%211 = llvm.load %126 : !llvm.ptr -> i64
%212 = arith.cmpi slt, %210, %211 : i64
cf.cond_br %212, ^bb40, ^bb41
^bb40:
%214 = llvm.load %209 : !llvm.ptr -> i64
%215 = llvm.getelementptr %111[%214] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%213 = llvm.load %215 : !llvm.ptr -> i64
%218 = llvm.load %209 : !llvm.ptr -> i64
%219 = llvm.getelementptr %160[%218] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%217 = llvm.load %219 : !llvm.ptr -> i64
%220 = arith.constant 2 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.subi %213, %222 : i64
%216 = func.call @modpow(%217, %221, %213) : (i64, i64, i64) -> i64
%223 = llvm.load %209 : !llvm.ptr -> i64
%224 = arith.constant 1 : i32
%226 = arith.extsi %224 : i32 to i64
%225 = arith.addi %223, %226 : i64
%228 = llvm.load %209 : !llvm.ptr -> i64
%229 = llvm.getelementptr %156[%228] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%227 = llvm.load %229 : !llvm.ptr -> i64
%230 = arith.subi %225, %227 : i64
%231 = arith.remsi %230, %213 : i64
%232 = arith.muli %231, %216 : i64
%233 = arith.remsi %232, %213 : i64
%234 = llvm.mlir.constant(1 : i64) : i64
%235 = llvm.alloca %234 x i64 : (i64) -> !llvm.ptr
llvm.store %233, %235 : i64, !llvm.ptr
%236 = llvm.load %235 : !llvm.ptr -> i64
%237 = arith.constant 0 : i32
%239 = arith.extsi %237 : i32 to i64
%238 = arith.cmpi slt, %236, %239 : i64
cf.cond_br %238, ^bb42, ^bb43
^bb42:
%240 = llvm.load %235 : !llvm.ptr -> i64
%241 = arith.addi %240, %213 : i64
llvm.store %241, %235 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%242 = llvm.load %209 : !llvm.ptr -> i64
%243 = arith.constant 1 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.addi %242, %245 : i64
llvm.store %244, %185 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%246 = llvm.load %185 : !llvm.ptr -> i64
%247 = llvm.load %126 : !llvm.ptr -> i64
%248 = arith.cmpi slt, %246, %247 : i64
cf.cond_br %248, ^bb46, ^bb47
^bb46:
%250 = llvm.load %185 : !llvm.ptr -> i64
%251 = llvm.getelementptr %111[%250] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%249 = llvm.load %251 : !llvm.ptr -> i64
%253 = llvm.load %185 : !llvm.ptr -> i64
%254 = llvm.getelementptr %156[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%252 = llvm.load %254 : !llvm.ptr -> i64
%256 = llvm.load %185 : !llvm.ptr -> i64
%257 = llvm.getelementptr %160[%256] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%255 = llvm.load %257 : !llvm.ptr -> i64
%258 = llvm.load %235 : !llvm.ptr -> i64
%259 = arith.muli %255, %258 : i64
%260 = arith.remsi %259, %249 : i64
%261 = arith.addi %252, %260 : i64
%262 = arith.remsi %261, %249 : i64
%263 = llvm.load %185 : !llvm.ptr -> i64
%264 = llvm.getelementptr %156[%263] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %262, %264 : i64, !llvm.ptr
%266 = llvm.load %185 : !llvm.ptr -> i64
%267 = llvm.getelementptr %160[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%265 = llvm.load %267 : !llvm.ptr -> i64
%268 = arith.muli %265, %213 : i64
%269 = arith.remsi %268, %249 : i64
%270 = llvm.load %185 : !llvm.ptr -> i64
%271 = llvm.getelementptr %160[%270] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %269, %271 : i64, !llvm.ptr
%272 = arith.constant 0 : i32
%274 = arith.extsi %272 : i32 to i64
%273 = arith.cmpi eq, %262, %274 : i64
cf.cond_br %273, ^bb48, ^bb49
^bb48:
%275 = arith.constant 1 : i32
%276 = llvm.load %185 : !llvm.ptr -> i64
%277 = arith.trunci %275 : i32 to i8
%278 = llvm.getelementptr %164[%276] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %277, %278 : i8, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%279 = llvm.load %185 : !llvm.ptr -> i64
%280 = arith.constant 1 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.addi %279, %282 : i64
llvm.store %281, %185 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%283 = llvm.load %209 : !llvm.ptr -> i64
%284 = arith.constant 1 : i32
%286 = arith.extsi %284 : i32 to i64
%285 = arith.addi %283, %286 : i64
llvm.store %285, %209 : i64, !llvm.ptr
cf.br ^bb39
^bb41:
%287 = arith.constant 0 : i32
%288 = arith.extsi %287 : i32 to i64
%289 = llvm.mlir.constant(1 : i64) : i64
%290 = llvm.alloca %289 x i64 : (i64) -> !llvm.ptr
llvm.store %288, %290 : i64, !llvm.ptr
%291 = arith.constant 0 : i32
%292 = arith.extsi %291 : i32 to i64
llvm.store %292, %185 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%293 = llvm.load %185 : !llvm.ptr -> i64
%294 = llvm.load %126 : !llvm.ptr -> i64
%295 = arith.cmpi slt, %293, %294 : i64
cf.cond_br %295, ^bb52, ^bb53
^bb52:
%297 = llvm.load %185 : !llvm.ptr -> i64
%298 = llvm.getelementptr %164[%297] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%296 = llvm.load %298 : !llvm.ptr -> i8
%299 = arith.constant 0 : i32
%301 = arith.extsi %296 : i8 to i32
%300 = arith.cmpi ne, %301, %299 : i32
cf.cond_br %300, ^bb54, ^bb55
^bb54:
%302 = llvm.load %290 : !llvm.ptr -> i64
%304 = llvm.load %185 : !llvm.ptr -> i64
%305 = llvm.getelementptr %111[%304] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%303 = llvm.load %305 : !llvm.ptr -> i64
%306 = arith.addi %302, %303 : i64
llvm.store %306, %290 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%307 = llvm.load %185 : !llvm.ptr -> i64
%308 = arith.constant 1 : i32
%310 = arith.extsi %308 : i32 to i64
%309 = arith.addi %307, %310 : i64
llvm.store %309, %185 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
func.call @free(%111) : (!llvm.ptr) -> ()
func.call @free(%156) : (!llvm.ptr) -> ()
func.call @free(%160) : (!llvm.ptr) -> ()
func.call @free(%164) : (!llvm.ptr) -> ()
%315 = llvm.load %290 : !llvm.ptr -> i64
func.return %315 : i64
}
func.func @main() -> i32 {
%316 = llvm.mlir.addressof @str_0 : !llvm.ptr
%318 = arith.constant 300000 : i32
%319 = arith.extsi %318 : i32 to i64
%317 = func.call @compute_S(%319) : (i64) -> i64
%320 = llvm.call @printf(%316, %317) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%321 = arith.constant 0 : i32
func.return %321 : i32
}
}