← All problems Problem 712
S(N) = sum over pairs (n, m) <= N of sum_p |nu_p(n) - nu_p(m)|. Per prime p the class counts are c_r = N/p^r - N/p^(r+1); the contribution is sum_{r<s} 2 c_r c_s (s - r). Primes up to sqrt(N) are handled directly; larger primes have exponent 0 or 1 and are grouped by q = N/p using a Lucy_Hedgehog prime counting sieve. N = 10^12, answer mod 1e9+7.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)O(n * m)Space complexity O(n)O(n)Approach Flow solution Dynamic programming or generating function Verdict Unknown
Flow source
# Project Euler 712: Exponent Difference
# S(N) = sum over pairs (n, m) <= N of sum_p |nu_p(n) - nu_p(m)|.
# Per prime p the class counts are c_r = N/p^r - N/p^(r+1); the contribution
# is sum_{r<s} 2 c_r c_s (s - r). Primes up to sqrt(N) are handled directly;
# larger primes have exponent 0 or 1 and are grouped by q = N/p using a
# Lucy_Hedgehog prime counting sieve. N = 10^12, answer mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
function main() -> i32 {
let N: i64 = 1000000000000
let r: i64 = 1000000
# Lucy_Hedgehog: small[i] = pi(i), large[i] = pi(N / i)
let small: ptr<i64> = calloc(r + 1, 8)
let large: ptr<i64> = calloc(r + 1, 8)
for i in 1..(r + 1) {
small[i] = i - 1
large[i] = N / i - 1
}
for p in 2..(r + 1) {
if small[p] > small[p - 1] {
let sp: i64 = small[p - 1]
let p2: i64 = (p as i64) * (p as i64)
let mut imax: i64 = N / p2
if imax > r { imax = r }
for i in 1..(imax + 1) {
let d: i64 = i * p
if d <= r {
large[i] = large[i] - (large[d] - sp)
} else {
large[i] = large[i] - (small[N / d] - sp)
}
}
let mut j: i64 = r
while j >= p2 {
small[j] = small[j] - (small[j / p] - sp)
j = j - 1
}
}
}
let mut total: i64 = 0
let cs: ptr<i64> = calloc(64, 8)
# Small primes p <= sqrt(N): full exponent distribution
for p in 2..(r + 1) {
if small[p] > small[p - 1] {
let mut k: i64 = 0
let mut pk: i64 = 1
while pk <= N {
cs[k] = N / pk - N / (pk * p)
k = k + 1
pk = pk * p
}
for a in 0..k {
for b in (a + 1)..k {
let mut t: i128 = (cs[a] as i128) * (cs[b] as i128) % (MOD as i128)
t = t * ((2 * (b - a)) as i128) % (MOD as i128)
total = (total + t as i64) % MOD
}
}
}
}
# Large primes p in (sqrt(N), N]: exponent 0 or 1, contribution 2*q*(N-q)
# per prime where q = N / p. Group primes by q via the pi tables.
let mut prev: i64 = small[r]
let mut plo: i64 = r + 1
while plo <= N {
let q: i64 = N / plo
let phi: i64 = N / q
let cp: i64 = large[q]
let cnt: i64 = cp - prev
if cnt > 0 {
let mut t: i128 = ((2 * q) as i128) * ((N - q) as i128) % (MOD as i128)
t = t * (cnt as i128) % (MOD as i128)
total = (total + t as i64) % MOD
}
prev = cp
plo = phi + 1
}
printf("%lld\n", total)
free(cs)
free(large)
free(small)
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; }
int32_t main(void);
static const int64_t MOD = 1000000007;
int32_t main(void) {
int64_t N = 1000000000000;
int64_t r = 1000000;
int64_t* small = (int64_t*)(calloc((r + 1), 8));
int64_t* large = (int64_t*)(calloc((r + 1), 8));
int32_t __flow_step_1 = 1;
for (int32_t i = 1; (1 <= (r + 1)) ? i < (r + 1) : i > (r + 1); i += (1 <= (r + 1)) ? 1 : -1) {
small[i] = (i - 1);
large[i] = (FLOW_CHECKED_DIV((N), (i)) - 1);
}
int32_t __flow_step_2 = 1;
for (int32_t p = 2; (2 <= (r + 1)) ? p < (r + 1) : p > (r + 1); p += (2 <= (r + 1)) ? 1 : -1) {
if (small[p] > small[(p - 1)]) {
int64_t sp = small[(p - 1)];
int64_t p2 = (((int64_t)(p)) * ((int64_t)(p)));
int64_t imax = FLOW_CHECKED_DIV((N), (p2));
if (imax > r) {
imax = r;
}
int32_t __flow_step_3 = 1;
for (int32_t i = 1; (1 <= (imax + 1)) ? i < (imax + 1) : i > (imax + 1); i += (1 <= (imax + 1)) ? 1 : -1) {
int64_t d = (i * p);
if (d <= r) {
large[i] = (large[i] - (large[d] - sp));
} else {
large[i] = (large[i] - (small[FLOW_CHECKED_DIV((N), (d))] - sp));
}
}
int64_t j = r;
while (j >= p2) {
small[j] = (small[j] - (small[FLOW_CHECKED_DIV((j), (p))] - sp));
j = (j - 1);
}
}
}
int64_t total = 0;
int64_t* cs = (int64_t*)(calloc(64, 8));
int32_t __flow_step_4 = 1;
for (int32_t p = 2; (2 <= (r + 1)) ? p < (r + 1) : p > (r + 1); p += (2 <= (r + 1)) ? 1 : -1) {
if (small[p] > small[(p - 1)]) {
int64_t k = 0;
int64_t pk = 1;
while (pk <= N) {
cs[k] = (FLOW_CHECKED_DIV((N), (pk)) - FLOW_CHECKED_DIV((N), ((pk * p))));
k = (k + 1);
pk = (pk * p);
}
int32_t __flow_step_5 = 1;
for (int32_t a = 0; (0 <= k) ? a < k : a > k; a += (0 <= k) ? 1 : -1) {
int32_t __flow_step_6 = 1;
for (int32_t b = (a + 1); ((a + 1) <= k) ? b < k : b > k; b += ((a + 1) <= k) ? 1 : -1) {
__int128 t = FLOW_CHECKED_MOD(((((__int128)(cs[a])) * ((__int128)(cs[b])))), (((__int128)(MOD))));
t = FLOW_CHECKED_MOD(((t * ((__int128)((2 * (b - a)))))), (((__int128)(MOD))));
total = FLOW_CHECKED_MOD(((total + ((int64_t)(t)))), (MOD));
}
}
}
}
int64_t prev = small[r];
int64_t plo = (r + 1);
while (plo <= N) {
int64_t q = FLOW_CHECKED_DIV((N), (plo));
int64_t phi = FLOW_CHECKED_DIV((N), (q));
int64_t cp = large[q];
int64_t cnt = (cp - prev);
if (cnt > 0) {
__int128 t = FLOW_CHECKED_MOD(((((__int128)((2 * q))) * ((__int128)((N - q))))), (((__int128)(MOD))));
t = FLOW_CHECKED_MOD(((t * ((__int128)(cnt)))), (((__int128)(MOD))));
total = FLOW_CHECKED_MOD(((total + ((int64_t)(t)))), (MOD));
}
prev = cp;
plo = (phi + 1);
}
printf("%lld\n", total);
free(cs);
free(large);
free(small);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @main() -> i32 {
%0 = arith.constant 995705032704 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = arith.constant 1000000 : i32
%3 = arith.extsi %2 : i32 to i64
%5 = arith.constant 1 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.addi %3, %7 : i64
%8 = arith.constant 8 : i32
%9 = arith.extsi %8 : i32 to i64
%4 = func.call @calloc(%6, %9) : (i64, i64) -> !llvm.ptr
%11 = arith.constant 1 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.addi %3, %13 : i64
%14 = arith.constant 8 : i32
%15 = arith.extsi %14 : i32 to i64
%10 = func.call @calloc(%12, %15) : (i64, i64) -> !llvm.ptr
%16 = arith.constant 1 : i32
%17 = arith.constant 1 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.addi %3, %19 : i64
%20 = arith.index_cast %16 : i32 to index
%21 = arith.index_cast %18 : i32 to index
%23 = arith.constant 1 : index
%24 = arith.constant -1 : index
%25 = arith.cmpi sle, %20, %21 : index
%22 = arith.select %25, %23, %24 : index
cf.br ^bb0(%20 : index)
^bb0(%26: index):
%27 = arith.cmpi slt, %26, %21 : index
%28 = arith.cmpi sgt, %26, %21 : index
%29 = arith.select %25, %27, %28 : i1
cf.cond_br %29, ^bb1(%26 : index), ^bb2(%26 : index)
^bb1(%30: index):
%31 = arith.constant 1 : i32
%33 = arith.index_cast %30 : index to i32
%32 = arith.subi %33, %31 : i32
%34 = arith.extsi %32 : i32 to i64
%35 = arith.index_cast %30 : index to i64
%36 = llvm.getelementptr %4[%35] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %34, %36 : i64, !llvm.ptr
%38 = arith.trunci %1 : i64 to i32
%39 = arith.index_cast %30 : index to i32
%37 = arith.divsi %38, %39 : i32
%40 = arith.constant 1 : i32
%41 = arith.subi %37, %40 : i32
%42 = arith.extsi %41 : i32 to i64
%43 = arith.index_cast %30 : index to i64
%44 = llvm.getelementptr %10[%43] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %42, %44 : i64, !llvm.ptr
%45 = arith.addi %30, %22 : index
cf.br ^bb0(%45 : index)
^bb2(%46: index):
%47 = arith.constant 2 : i32
%48 = arith.constant 1 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.addi %3, %50 : i64
%51 = arith.index_cast %47 : i32 to index
%52 = arith.index_cast %49 : i32 to index
%54 = arith.constant 1 : index
%55 = arith.constant -1 : index
%56 = arith.cmpi sle, %51, %52 : index
%53 = arith.select %56, %54, %55 : index
cf.br ^bb3(%51 : index)
^bb3(%57: index):
%58 = arith.cmpi slt, %57, %52 : index
%59 = arith.cmpi sgt, %57, %52 : index
%60 = arith.select %56, %58, %59 : i1
cf.cond_br %60, ^bb4(%57 : index), ^bb5(%57 : index)
^bb4(%61: index):
%63 = arith.index_cast %61 : index to i64
%64 = llvm.getelementptr %4[%63] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%62 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.constant 1 : i32
%68 = arith.index_cast %61 : index to i32
%67 = arith.subi %68, %66 : i32
%69 = arith.extsi %67 : i32 to i64
%70 = llvm.getelementptr %4[%69] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%65 = llvm.load %70 : !llvm.ptr -> i64
%71 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %71, ^bb6, ^bb7
^bb6:
%73 = arith.constant 1 : i32
%75 = arith.index_cast %61 : index to i32
%74 = arith.subi %75, %73 : i32
%76 = arith.extsi %74 : i32 to i64
%77 = llvm.getelementptr %4[%76] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%72 = llvm.load %77 : !llvm.ptr -> i64
%78 = arith.index_cast %61 : index to i64
%79 = arith.index_cast %61 : index to i64
%80 = arith.muli %78, %79 : i64
%81 = arith.divsi %1, %80 : i64
%82 = llvm.mlir.constant(1 : i64) : i64
%83 = llvm.alloca %82 x i64 : (i64) -> !llvm.ptr
llvm.store %81, %83 : i64, !llvm.ptr
%84 = llvm.load %83 : !llvm.ptr -> i64
%85 = arith.cmpi sgt, %84, %3 : i64
cf.cond_br %85, ^bb9, ^bb10
^bb9:
llvm.store %3, %83 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%86 = arith.constant 1 : i32
%87 = llvm.load %83 : !llvm.ptr -> i64
%88 = arith.constant 1 : i32
%90 = arith.extsi %88 : i32 to i64
%89 = arith.addi %87, %90 : i64
%91 = arith.index_cast %86 : i32 to index
%92 = arith.index_cast %89 : i32 to index
%94 = arith.constant 1 : index
%95 = arith.constant -1 : index
%96 = arith.cmpi sle, %91, %92 : index
%93 = arith.select %96, %94, %95 : index
cf.br ^bb12(%91 : index)
^bb12(%97: index):
%98 = arith.cmpi slt, %97, %92 : index
%99 = arith.cmpi sgt, %97, %92 : index
%100 = arith.select %96, %98, %99 : i1
cf.cond_br %100, ^bb13(%97 : index), ^bb14(%97 : index)
^bb13(%101: index):
%102 = arith.muli %101, %61 : index
%103 = arith.index_cast %102 : index to i64
%104 = arith.cmpi sle, %103, %3 : i64
cf.cond_br %104, ^bb15, ^bb16
^bb15:
%106 = arith.index_cast %101 : index to i64
%107 = llvm.getelementptr %10[%106] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%105 = llvm.load %107 : !llvm.ptr -> i64
%109 = llvm.getelementptr %10[%103] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%108 = llvm.load %109 : !llvm.ptr -> i64
%110 = arith.subi %108, %72 : i64
%111 = arith.subi %105, %110 : i64
%112 = arith.index_cast %101 : index to i64
%113 = llvm.getelementptr %10[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %111, %113 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
%115 = arith.index_cast %101 : index to i64
%116 = llvm.getelementptr %10[%115] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%114 = llvm.load %116 : !llvm.ptr -> i64
%118 = arith.divsi %1, %103 : i64
%119 = llvm.getelementptr %4[%118] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%117 = llvm.load %119 : !llvm.ptr -> i64
%120 = arith.subi %117, %72 : i64
%121 = arith.subi %114, %120 : i64
%122 = arith.index_cast %101 : index to i64
%123 = llvm.getelementptr %10[%122] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %121, %123 : i64, !llvm.ptr
cf.br ^bb17
^bb17:
%124 = arith.addi %101, %93 : index
cf.br ^bb12(%124 : index)
^bb14(%125: index):
%126 = llvm.mlir.constant(1 : i64) : i64
%127 = llvm.alloca %126 x i64 : (i64) -> !llvm.ptr
llvm.store %3, %127 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%128 = llvm.load %127 : !llvm.ptr -> i64
%129 = arith.cmpi sge, %128, %80 : i64
cf.cond_br %129, ^bb19, ^bb20
^bb19:
%131 = llvm.load %127 : !llvm.ptr -> i64
%132 = llvm.getelementptr %4[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%130 = llvm.load %132 : !llvm.ptr -> i64
%134 = llvm.load %127 : !llvm.ptr -> i64
%136 = arith.trunci %134 : i64 to i32
%137 = arith.index_cast %61 : index to i32
%135 = arith.divsi %136, %137 : i32
%138 = arith.extsi %135 : i32 to i64
%139 = llvm.getelementptr %4[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%133 = llvm.load %139 : !llvm.ptr -> i64
%140 = arith.subi %133, %72 : i64
%141 = arith.subi %130, %140 : i64
%142 = llvm.load %127 : !llvm.ptr -> i64
%143 = llvm.getelementptr %4[%142] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %141, %143 : i64, !llvm.ptr
%144 = llvm.load %127 : !llvm.ptr -> i64
%145 = arith.constant 1 : i32
%147 = arith.extsi %145 : i32 to i64
%146 = arith.subi %144, %147 : i64
llvm.store %146, %127 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%148 = arith.addi %61, %53 : index
cf.br ^bb3(%148 : index)
^bb5(%149: index):
%150 = arith.constant 0 : i32
%151 = arith.extsi %150 : i32 to i64
%152 = llvm.mlir.constant(1 : i64) : i64
%153 = llvm.alloca %152 x i64 : (i64) -> !llvm.ptr
llvm.store %151, %153 : i64, !llvm.ptr
%155 = arith.constant 64 : i32
%156 = arith.constant 8 : i32
%157 = arith.extsi %155 : i32 to i64
%158 = arith.extsi %156 : i32 to i64
%154 = func.call @calloc(%157, %158) : (i64, i64) -> !llvm.ptr
%159 = arith.constant 2 : i32
%160 = arith.constant 1 : i32
%162 = arith.extsi %160 : i32 to i64
%161 = arith.addi %3, %162 : i64
%163 = arith.index_cast %159 : i32 to index
%164 = arith.index_cast %161 : i32 to index
%166 = arith.constant 1 : index
%167 = arith.constant -1 : index
%168 = arith.cmpi sle, %163, %164 : index
%165 = arith.select %168, %166, %167 : index
cf.br ^bb21(%163 : index)
^bb21(%169: index):
%170 = arith.cmpi slt, %169, %164 : index
%171 = arith.cmpi sgt, %169, %164 : index
%172 = arith.select %168, %170, %171 : i1
cf.cond_br %172, ^bb22(%169 : index), ^bb23(%169 : index)
^bb22(%173: index):
%175 = arith.index_cast %173 : index to i64
%176 = llvm.getelementptr %4[%175] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%174 = llvm.load %176 : !llvm.ptr -> i64
%178 = arith.constant 1 : i32
%180 = arith.index_cast %173 : index to i32
%179 = arith.subi %180, %178 : i32
%181 = arith.extsi %179 : i32 to i64
%182 = llvm.getelementptr %4[%181] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%177 = llvm.load %182 : !llvm.ptr -> i64
%183 = arith.cmpi sgt, %174, %177 : i64
cf.cond_br %183, ^bb24, ^bb25
^bb24:
%184 = arith.constant 0 : i32
%185 = arith.extsi %184 : i32 to i64
%186 = llvm.mlir.constant(1 : i64) : i64
%187 = llvm.alloca %186 x i64 : (i64) -> !llvm.ptr
llvm.store %185, %187 : i64, !llvm.ptr
%188 = arith.constant 1 : 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
cf.br ^bb27
^bb27:
%192 = llvm.load %191 : !llvm.ptr -> i64
%193 = arith.cmpi sle, %192, %1 : i64
cf.cond_br %193, ^bb28, ^bb29
^bb28:
%194 = llvm.load %191 : !llvm.ptr -> i64
%195 = arith.divsi %1, %194 : i64
%196 = llvm.load %191 : !llvm.ptr -> i64
%198 = arith.trunci %196 : i64 to i32
%199 = arith.index_cast %173 : index to i32
%197 = arith.muli %198, %199 : i32
%201 = arith.extsi %197 : i32 to i64
%200 = arith.divsi %1, %201 : i64
%202 = arith.subi %195, %200 : i64
%203 = llvm.load %187 : !llvm.ptr -> i64
%204 = llvm.getelementptr %154[%203] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %202, %204 : i64, !llvm.ptr
%205 = llvm.load %187 : !llvm.ptr -> i64
%206 = arith.constant 1 : i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.addi %205, %208 : i64
llvm.store %207, %187 : i64, !llvm.ptr
%209 = llvm.load %191 : !llvm.ptr -> i64
%211 = arith.trunci %209 : i64 to i32
%212 = arith.index_cast %173 : index to i32
%210 = arith.muli %211, %212 : i32
%213 = arith.extsi %210 : i32 to i64
llvm.store %213, %191 : i64, !llvm.ptr
cf.br ^bb27
^bb29:
%214 = arith.constant 0 : i32
%215 = llvm.load %187 : !llvm.ptr -> i64
%216 = arith.index_cast %214 : i32 to index
%217 = arith.index_cast %215 : i32 to index
%219 = arith.constant 1 : index
%220 = arith.constant -1 : index
%221 = arith.cmpi sle, %216, %217 : index
%218 = arith.select %221, %219, %220 : index
cf.br ^bb30(%216 : index)
^bb30(%222: index):
%223 = arith.cmpi slt, %222, %217 : index
%224 = arith.cmpi sgt, %222, %217 : index
%225 = arith.select %221, %223, %224 : i1
cf.cond_br %225, ^bb31(%222 : index), ^bb32(%222 : index)
^bb31(%226: index):
%227 = arith.constant 1 : i32
%229 = arith.index_cast %226 : index to i32
%228 = arith.addi %229, %227 : i32
%230 = llvm.load %187 : !llvm.ptr -> i64
%231 = arith.index_cast %228 : i32 to index
%232 = arith.index_cast %230 : i32 to index
%234 = arith.constant 1 : index
%235 = arith.constant -1 : index
%236 = arith.cmpi sle, %231, %232 : index
%233 = arith.select %236, %234, %235 : index
cf.br ^bb33(%231 : index)
^bb33(%237: index):
%238 = arith.cmpi slt, %237, %232 : index
%239 = arith.cmpi sgt, %237, %232 : index
%240 = arith.select %236, %238, %239 : i1
cf.cond_br %240, ^bb34(%237 : index), ^bb35(%237 : index)
^bb34(%241: index):
%243 = arith.index_cast %226 : index to i64
%244 = llvm.getelementptr %154[%243] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%242 = llvm.load %244 : !llvm.ptr -> i64
%245 = arith.extsi %242 : i64 to i128
%247 = arith.index_cast %241 : index to i64
%248 = llvm.getelementptr %154[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%246 = llvm.load %248 : !llvm.ptr -> i64
%249 = arith.extsi %246 : i64 to i128
%251 = arith.trunci %245 : i128 to i64
%252 = arith.trunci %249 : i128 to i64
%250 = arith.muli %251, %252 : i64
%253 = llvm.mlir.addressof @MOD : !llvm.ptr
%254 = llvm.load %253 : !llvm.ptr -> i64
%255 = arith.extsi %254 : i64 to i128
%257 = arith.trunci %255 : i128 to i64
%256 = arith.remsi %250, %257 : i64
%258 = arith.extsi %256 : i64 to i128
%259 = llvm.mlir.constant(1 : i64) : i64
%260 = llvm.alloca %259 x i128 : (i64) -> !llvm.ptr
llvm.store %258, %260 : i128, !llvm.ptr
%261 = llvm.load %260 : !llvm.ptr -> i128
%262 = arith.constant 2 : i32
%263 = arith.subi %241, %226 : index
%265 = arith.index_cast %263 : index to i32
%264 = arith.muli %262, %265 : i32
%266 = arith.extsi %264 : i32 to i128
%268 = arith.trunci %261 : i128 to i64
%269 = arith.trunci %266 : i128 to i64
%267 = arith.muli %268, %269 : i64
%270 = llvm.mlir.addressof @MOD : !llvm.ptr
%271 = llvm.load %270 : !llvm.ptr -> i64
%272 = arith.extsi %271 : i64 to i128
%274 = arith.trunci %272 : i128 to i64
%273 = arith.remsi %267, %274 : i64
%275 = arith.extsi %273 : i64 to i128
llvm.store %275, %260 : i128, !llvm.ptr
%276 = llvm.load %153 : !llvm.ptr -> i64
%277 = llvm.load %260 : !llvm.ptr -> i128
%278 = arith.trunci %277 : i128 to i64
%279 = arith.addi %276, %278 : i64
%280 = llvm.mlir.addressof @MOD : !llvm.ptr
%281 = llvm.load %280 : !llvm.ptr -> i64
%282 = arith.remsi %279, %281 : i64
llvm.store %282, %153 : i64, !llvm.ptr
%283 = arith.addi %241, %233 : index
cf.br ^bb33(%283 : index)
^bb35(%284: index):
%285 = arith.addi %226, %218 : index
cf.br ^bb30(%285 : index)
^bb32(%286: index):
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%287 = arith.addi %173, %165 : index
cf.br ^bb21(%287 : index)
^bb23(%288: index):
%290 = llvm.getelementptr %4[%3] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%289 = llvm.load %290 : !llvm.ptr -> i64
%291 = llvm.mlir.constant(1 : i64) : i64
%292 = llvm.alloca %291 x i64 : (i64) -> !llvm.ptr
llvm.store %289, %292 : i64, !llvm.ptr
%293 = arith.constant 1 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.addi %3, %295 : i64
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
llvm.store %294, %297 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%298 = llvm.load %297 : !llvm.ptr -> i64
%299 = arith.cmpi sle, %298, %1 : i64
cf.cond_br %299, ^bb37, ^bb38
^bb37:
%300 = llvm.load %297 : !llvm.ptr -> i64
%301 = arith.divsi %1, %300 : i64
%302 = arith.divsi %1, %301 : i64
%304 = llvm.getelementptr %10[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%303 = llvm.load %304 : !llvm.ptr -> i64
%305 = llvm.load %292 : !llvm.ptr -> i64
%306 = arith.subi %303, %305 : i64
%307 = arith.constant 0 : i32
%309 = arith.extsi %307 : i32 to i64
%308 = arith.cmpi sgt, %306, %309 : i64
cf.cond_br %308, ^bb39, ^bb40
^bb39:
%310 = arith.constant 2 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.muli %312, %301 : i64
%313 = arith.extsi %311 : i64 to i128
%314 = arith.subi %1, %301 : i64
%315 = arith.extsi %314 : i64 to i128
%317 = arith.trunci %313 : i128 to i64
%318 = arith.trunci %315 : i128 to i64
%316 = arith.muli %317, %318 : i64
%319 = llvm.mlir.addressof @MOD : !llvm.ptr
%320 = llvm.load %319 : !llvm.ptr -> i64
%321 = arith.extsi %320 : i64 to i128
%323 = arith.trunci %321 : i128 to i64
%322 = arith.remsi %316, %323 : i64
%324 = arith.extsi %322 : i64 to i128
%325 = llvm.mlir.constant(1 : i64) : i64
%326 = llvm.alloca %325 x i128 : (i64) -> !llvm.ptr
llvm.store %324, %326 : i128, !llvm.ptr
%327 = llvm.load %326 : !llvm.ptr -> i128
%328 = arith.extsi %306 : i64 to i128
%330 = arith.trunci %327 : i128 to i64
%331 = arith.trunci %328 : i128 to i64
%329 = arith.muli %330, %331 : i64
%332 = llvm.mlir.addressof @MOD : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> i64
%334 = arith.extsi %333 : i64 to i128
%336 = arith.trunci %334 : i128 to i64
%335 = arith.remsi %329, %336 : i64
%337 = arith.extsi %335 : i64 to i128
llvm.store %337, %326 : i128, !llvm.ptr
%338 = llvm.load %153 : !llvm.ptr -> i64
%339 = llvm.load %326 : !llvm.ptr -> i128
%340 = arith.trunci %339 : i128 to i64
%341 = arith.addi %338, %340 : i64
%342 = llvm.mlir.addressof @MOD : !llvm.ptr
%343 = llvm.load %342 : !llvm.ptr -> i64
%344 = arith.remsi %341, %343 : i64
llvm.store %344, %153 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
llvm.store %303, %292 : i64, !llvm.ptr
%345 = arith.constant 1 : i32
%347 = arith.extsi %345 : i32 to i64
%346 = arith.addi %302, %347 : i64
llvm.store %346, %297 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%348 = llvm.mlir.addressof @str_0 : !llvm.ptr
%349 = llvm.load %153 : !llvm.ptr -> i64
%350 = llvm.call @printf(%348, %349) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%154) : (!llvm.ptr) -> ()
func.call @free(%10) : (!llvm.ptr) -> ()
func.call @free(%4) : (!llvm.ptr) -> ()
%354 = arith.constant 0 : i32
func.return %354 : i32
}
}