← All problems Problem 880
Nested Radicals: Compute H(10^15) mod (1031^3 + 2).
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(sqrt(n))Space complexity O(n)O(1)Approach Flow solution Trial division or Pollard rho Verdict Suboptimal
Flow source
# Project Euler 880
# Nested Radicals: Compute H(10^15) mod (1031^3 + 2).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function sqrt(x: f64) -> f64
function log(x: f64) -> f64
function exp(x: f64) -> f64
function round(x: f64) -> f64
}
const MOD: i64 = 1095912793
const N: i64 = 1000000000000000
let mut g_spf: ptr<i32> = null
function icbrt(n: i64) -> i64 {
if n <= 1 { return n }
let mut r: i64 = round(exp(log(n as f64) / 3.0)) as i64
while (r + 1) * (r + 1) * (r + 1) <= n { r = r + 1 }
while r * r * r > n { r = r - 1 }
return r
}
function iroot4(n: i64) -> i64 {
let mut r: i64 = (n as f64 |> sqrt |> sqrt) as i64
let n128: i128 = n as i128
while ((r + 1) as i128) * ((r + 1) as i128) * ((r + 1) as i128) * ((r + 1) as i128) <= n128 { r = r + 1 }
while (r as i128) * (r as i128) * (r as i128) * (r as i128) > n128 { r = r - 1 }
return r
}
function isqrt_ll(n: i64) -> i64 {
if n < 0 { return 0 }
let mut r: i64 = sqrt(n as f64) as i64
while (r + 1) * (r + 1) <= n { r = r + 1 }
while r * r > n { r = r - 1 }
return r
}
function gcd_int(a0: i32, b0: i32) -> i32 {
let mut a: i32 = a0
let mut b: i32 = b0
while b != 0 {
let t: i32 = a % b
a = b
b = t
}
return a
}
function build_spf(limit: i32) -> void {
g_spf = calloc((limit + 1) as i64, 4)
let mut i: i32 = 0
while i <= limit {
g_spf[i] = i
i = i + 1
}
g_spf[1] = 1
let mut p: i32 = 2
while (p as i64) * (p as i64) <= (limit as i64) {
if g_spf[p] == p {
let mut m: i32 = p * p
while m <= limit {
if g_spf[m] == m { g_spf[m] = p }
m = m + p
}
}
p = p + 1
}
}
function cube_free_table(limit: i32) -> ptr<i32> {
build_spf(limit)
let cf: ptr<i32> = calloc((limit + 1) as i64, 4)
cf[0] = 1
cf[1] = 1
let mut n: i32 = 2
while n <= limit {
let p: i32 = g_spf[n]
let mut m: i32 = n / p
let mut e: i32 = 1
while m % p == 0 {
m = m / p
e = e + 1
}
let rem: i32 = e % 3
if rem == 0 {
cf[n] = cf[m]
} else {
if rem == 1 {
cf[n] = cf[m] * p
} else {
cf[n] = cf[m] * p * p
}
}
n = n + 1
}
return cf
}
function sumsq_mod(k: i64, mod: i64) -> i64 {
let val: i128 = (k as i128) * ((k + 1) as i128) * ((2 * k + 1) as i128) / 6
return (val % (mod as i128)) as i64
}
function mulmod(a0: i64, b0: i64, m: i64) -> i64 {
let a_w: i128 = a0 as i128
let b_w: i128 = b0 as i128
let m_w: i128 = m as i128
let r: i128 = (a_w * b_w) % m_w
return r as i64
}
function H_mod(limit: i64) -> i64 {
let b_limit: i64 = iroot4(4 * limit)
let mut max_odd_a: i64 = 0
let c_odd: i64 = icbrt(limit)
if c_odd > 1 { max_odd_a = (c_odd - 1) / 4 }
let mut max_even_a: i64 = 0
let c_even: i64 = icbrt(limit / 4)
if c_even > 1 { max_even_a = (c_even - 1) / 2 }
let mut cf_limit_val: i64 = 4 * max_odd_a
if max_even_a > cf_limit_val { cf_limit_val = max_even_a }
if 2 * b_limit > cf_limit_val { cf_limit_val = 2 * b_limit }
let cf_limit: i32 = cf_limit_val as i32
let cf: ptr<i32> = cube_free_table(cf_limit)
let cf4: ptr<i32> = calloc(max_odd_a + 1, 4)
cf4[0] = 0
let mut a_init: i64 = 1
while a_init <= max_odd_a {
cf4[a_init] = cf[4 * a_init]
a_init = a_init + 1
}
let mut total: i64 = 0
let mod_val: i64 = MOD
# Odd b
let mut b: i64 = 1
while b <= b_limit {
let a_limit: i64 = (icbrt(limit / b) - b) / 4
let cf_b: i32 = cf[b]
let mut a: i64 = 1
while a <= a_limit {
if gcd_int(a as i32, b as i32) == 1 && cf_b != cf4[a] {
let x_base: i64 = b + 4 * a
let x: i128 = (b as i128) * (x_base as i128) * (x_base as i128) * (x_base as i128)
let y_base: i64 = a - 2 * b
let yc: i128 = (y_base as i128) * (y_base as i128) * (y_base as i128)
let mut yc_abs: i128 = yc
if yc_abs < 0 { yc_abs = 0 - yc_abs }
let y_abs: i128 = 4 * (a as i128) * yc_abs
let mut max_coord: i128 = x
if y_abs > x { max_coord = y_abs }
if max_coord <= (limit as i128) {
let mc: i64 = max_coord as i64
let tmax: i64 = isqrt_ll(limit / mc)
let s: i64 = sumsq_mod(tmax, mod_val)
let xy_mod: i64 = ((x + y_abs) % (mod_val as i128)) as i64
let contribution: i64 = mulmod(xy_mod, s, mod_val)
total = (total + contribution) % mod_val
}
}
a = a + 1
}
b = b + 2
}
# Even b
b = 2
while b <= b_limit {
let half_b: i64 = b / 2
let a_limit: i64 = (icbrt(limit / (2 * b)) - half_b) / 2
let cf_2b: i32 = cf[2 * b]
let mut a: i64 = 1
while a <= a_limit {
if gcd_int(a as i32, b as i32) == 1 && cf_2b != cf[a] {
let x_base: i64 = half_b + 2 * a
let x: i128 = (2 as i128) * (b as i128) * (x_base as i128) * (x_base as i128) * (x_base as i128)
let y_base: i64 = a - 2 * b
let yc: i128 = (y_base as i128) * (y_base as i128) * (y_base as i128)
let mut yc_abs: i128 = yc
if yc_abs < 0 { yc_abs = 0 - yc_abs }
let y_abs: i128 = (a as i128) * yc_abs
let mut max_coord: i128 = x
if y_abs > x { max_coord = y_abs }
if max_coord <= (limit as i128) {
let mc: i64 = max_coord as i64
let tmax: i64 = isqrt_ll(limit / mc)
let s: i64 = sumsq_mod(tmax, mod_val)
let xy_mod: i64 = ((x + y_abs) % (mod_val as i128)) as i64
let contribution: i64 = mulmod(xy_mod, s, mod_val)
total = (total + contribution) % mod_val
}
}
a = a + 2
}
b = b + 2
}
free(cf)
free(cf4)
free(g_spf)
return total
}
function main() -> i32 {
let ans: i64 = H_mod(N) % MOD
printf("%lld\n", ans)
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 icbrt_i64(int64_t n);
int64_t iroot4_i64(int64_t n);
int64_t isqrt_ll_i64(int64_t n);
int32_t gcd_int_i32_i32(int32_t a0, int32_t b0);
void build_spf_i32(int32_t limit);
int32_t* cube_free_table_i32(int32_t limit);
int64_t sumsq_mod_i64_i64(int64_t k, int64_t mod);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t m);
int64_t H_mod_i64(int64_t limit);
int32_t main(void);
static const int64_t MOD = 1095912793;
static const int64_t N = 1000000000000000;
/* Module statics */
static int32_t* g_spf = NULL;
int64_t icbrt_i64(int64_t n) {
if (n <= 1) {
return n;
}
int64_t r = ((int64_t)(round(exp((log(((double)(n))) / 3.0)))));
while ((((r + 1) * (r + 1)) * (r + 1)) <= n) {
r = (r + 1);
}
while (((r * r) * r) > n) {
r = (r - 1);
}
return r;
}
int64_t iroot4_i64(int64_t n) {
int64_t r = ((int64_t)(sqrt(sqrt(((double)(n))))));
__int128 n128 = ((__int128)(n));
while ((((((__int128)((r + 1))) * ((__int128)((r + 1)))) * ((__int128)((r + 1)))) * ((__int128)((r + 1)))) <= n128) {
r = (r + 1);
}
while ((((((__int128)(r)) * ((__int128)(r))) * ((__int128)(r))) * ((__int128)(r))) > n128) {
r = (r - 1);
}
return r;
}
int64_t isqrt_ll_i64(int64_t n) {
if (n < 0) {
return 0;
}
int64_t r = ((int64_t)(sqrt(((double)(n)))));
while (((r + 1) * (r + 1)) <= n) {
r = (r + 1);
}
while ((r * r) > n) {
r = (r - 1);
}
return r;
}
int32_t gcd_int_i32_i32(int32_t a0, int32_t b0) {
int32_t a = a0;
int32_t b = b0;
while (b != 0) {
int32_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
void build_spf_i32(int32_t limit) {
g_spf = calloc(((int64_t)((limit + 1))), 4);
int32_t i = 0;
while (i <= limit) {
g_spf[i] = i;
i = (i + 1);
}
g_spf[1] = 1;
int32_t p = 2;
while ((((int64_t)(p)) * ((int64_t)(p))) <= ((int64_t)(limit))) {
if (g_spf[p] == p) {
int32_t m = (p * p);
while (m <= limit) {
if (g_spf[m] == m) {
g_spf[m] = p;
}
m = (m + p);
}
}
p = (p + 1);
}
}
int32_t* cube_free_table_i32(int32_t limit) {
build_spf_i32(limit);
int32_t* cf = (int32_t*)(calloc(((int64_t)((limit + 1))), 4));
cf[0] = 1;
cf[1] = 1;
int32_t n = 2;
while (n <= limit) {
int32_t p = g_spf[n];
int32_t m = FLOW_CHECKED_DIV((n), (p));
int32_t e = 1;
while (FLOW_CHECKED_MOD((m), (p)) == 0) {
m = FLOW_CHECKED_DIV((m), (p));
e = (e + 1);
}
int32_t rem = FLOW_CHECKED_MOD((e), (3));
if (rem == 0) {
cf[n] = cf[m];
} else {
if (rem == 1) {
cf[n] = (cf[m] * p);
} else {
cf[n] = ((cf[m] * p) * p);
}
}
n = (n + 1);
}
return cf;
}
int64_t sumsq_mod_i64_i64(int64_t k, int64_t mod) {
__int128 val = FLOW_CHECKED_DIV((((((__int128)(k)) * ((__int128)((k + 1)))) * ((__int128)(((2 * k) + 1))))), (6));
return ((int64_t)(FLOW_CHECKED_MOD((val), (((__int128)(mod))))));
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t m) {
__int128 a_w = ((__int128)(a0));
__int128 b_w = ((__int128)(b0));
__int128 m_w = ((__int128)(m));
__int128 r = FLOW_CHECKED_MOD(((a_w * b_w)), (m_w));
return ((int64_t)(r));
}
int64_t H_mod_i64(int64_t limit) {
int64_t b_limit = iroot4_i64((4 * limit));
int64_t max_odd_a = 0;
int64_t c_odd = icbrt_i64(limit);
if (c_odd > 1) {
max_odd_a = FLOW_CHECKED_DIV(((c_odd - 1)), (4));
}
int64_t max_even_a = 0;
int64_t c_even = icbrt_i64(FLOW_CHECKED_DIV((limit), (4)));
if (c_even > 1) {
max_even_a = FLOW_CHECKED_DIV(((c_even - 1)), (2));
}
int64_t cf_limit_val = (4 * max_odd_a);
if (max_even_a > cf_limit_val) {
cf_limit_val = max_even_a;
}
if ((2 * b_limit) > cf_limit_val) {
cf_limit_val = (2 * b_limit);
}
int32_t cf_limit = ((int32_t)(cf_limit_val));
int32_t* cf = (int32_t*)(cube_free_table_i32(cf_limit));
int32_t* cf4 = (int32_t*)(calloc((max_odd_a + 1), 4));
cf4[0] = 0;
int64_t a_init = 1;
while (a_init <= max_odd_a) {
cf4[a_init] = cf[(4 * a_init)];
a_init = (a_init + 1);
}
int64_t total = 0;
int64_t mod_val = MOD;
int64_t b = 1;
while (b <= b_limit) {
int64_t a_limit = FLOW_CHECKED_DIV(((icbrt_i64(FLOW_CHECKED_DIV((limit), (b))) - b)), (4));
int32_t cf_b = cf[b];
int64_t a = 1;
while (a <= a_limit) {
if ((gcd_int_i32_i32(((int32_t)(a)), ((int32_t)(b))) == 1 && cf_b != cf4[a])) {
int64_t x_base = (b + (4 * a));
__int128 x = (((((__int128)(b)) * ((__int128)(x_base))) * ((__int128)(x_base))) * ((__int128)(x_base)));
int64_t y_base = (a - (2 * b));
__int128 yc = ((((__int128)(y_base)) * ((__int128)(y_base))) * ((__int128)(y_base)));
__int128 yc_abs = yc;
if (yc_abs < 0) {
yc_abs = (0 - yc_abs);
}
__int128 y_abs = ((4 * ((__int128)(a))) * yc_abs);
__int128 max_coord = x;
if (y_abs > x) {
max_coord = y_abs;
}
if (max_coord <= ((__int128)(limit))) {
int64_t mc = ((int64_t)(max_coord));
int64_t tmax = isqrt_ll_i64(FLOW_CHECKED_DIV((limit), (mc)));
int64_t s = sumsq_mod_i64_i64(tmax, mod_val);
int64_t xy_mod = ((int64_t)(FLOW_CHECKED_MOD(((x + y_abs)), (((__int128)(mod_val))))));
int64_t contribution = mulmod_i64_i64_i64(xy_mod, s, mod_val);
total = FLOW_CHECKED_MOD(((total + contribution)), (mod_val));
}
}
a = (a + 1);
}
b = (b + 2);
}
b = 2;
while (b <= b_limit) {
int64_t half_b = FLOW_CHECKED_DIV((b), (2));
int64_t a_limit = FLOW_CHECKED_DIV(((icbrt_i64(FLOW_CHECKED_DIV((limit), ((2 * b)))) - half_b)), (2));
int32_t cf_2b = cf[(2 * b)];
int64_t a = 1;
while (a <= a_limit) {
if ((gcd_int_i32_i32(((int32_t)(a)), ((int32_t)(b))) == 1 && cf_2b != cf[a])) {
int64_t x_base = (half_b + (2 * a));
__int128 x = ((((((__int128)(2)) * ((__int128)(b))) * ((__int128)(x_base))) * ((__int128)(x_base))) * ((__int128)(x_base)));
int64_t y_base = (a - (2 * b));
__int128 yc = ((((__int128)(y_base)) * ((__int128)(y_base))) * ((__int128)(y_base)));
__int128 yc_abs = yc;
if (yc_abs < 0) {
yc_abs = (0 - yc_abs);
}
__int128 y_abs = (((__int128)(a)) * yc_abs);
__int128 max_coord = x;
if (y_abs > x) {
max_coord = y_abs;
}
if (max_coord <= ((__int128)(limit))) {
int64_t mc = ((int64_t)(max_coord));
int64_t tmax = isqrt_ll_i64(FLOW_CHECKED_DIV((limit), (mc)));
int64_t s = sumsq_mod_i64_i64(tmax, mod_val);
int64_t xy_mod = ((int64_t)(FLOW_CHECKED_MOD(((x + y_abs)), (((__int128)(mod_val))))));
int64_t contribution = mulmod_i64_i64_i64(xy_mod, s, mod_val);
total = FLOW_CHECKED_MOD(((total + contribution)), (mod_val));
}
}
a = (a + 2);
}
b = (b + 2);
}
free(cf);
free(cf4);
free(g_spf);
return total;
}
int32_t main(void) {
int64_t ans = FLOW_CHECKED_MOD((H_mod_i64(N)), (MOD));
printf("%lld\n", ans);
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 private @sqrt(f64) -> f64
func.func private @log(f64) -> f64
func.func private @exp(f64) -> f64
func.func private @round(f64) -> f64
// Constant: MOD
llvm.mlir.global internal constant @MOD(1095912793 : i64) : i64
// Constant: N
llvm.mlir.global internal constant @N(1000000000000000 : i64) : i64
// Module static: g_spf
llvm.mlir.global internal @g_spf() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
func.func @icbrt(%arg0: i64) -> i64 {
%1 = arith.constant 1 : i32
%3 = arith.extsi %1 : i32 to i64
%2 = arith.cmpi sle, %arg0, %3 : i64
cf.cond_br %2, ^bb0, ^bb1
^bb0:
func.return %arg0 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = arith.sitofp %arg0 : i64 to f64
%6 = math.log %5 : f64
%7 = arith.constant 3.0 : f32
%9 = arith.extf %7 : f32 to f64
%8 = arith.divf %6, %9 : f64
%10 = math.exp %8 : f64
%4 = func.call @round(%10) : (f64) -> f64
%11 = arith.fptosi %4 : f64 to i64
%12 = llvm.mlir.constant(1 : i64) : i64
%13 = llvm.alloca %12 x i64 : (i64) -> !llvm.ptr
llvm.store %11, %13 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%14 = llvm.load %13 : !llvm.ptr -> i64
%15 = arith.constant 1 : i32
%17 = arith.extsi %15 : i32 to i64
%16 = arith.addi %14, %17 : i64
%18 = llvm.load %13 : !llvm.ptr -> i64
%19 = arith.constant 1 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.addi %18, %21 : i64
%22 = arith.muli %16, %20 : i64
%23 = llvm.load %13 : !llvm.ptr -> i64
%24 = arith.constant 1 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.addi %23, %26 : i64
%27 = arith.muli %22, %25 : i64
%28 = arith.cmpi sle, %27, %arg0 : i64
cf.cond_br %28, ^bb4, ^bb5
^bb4:
%29 = llvm.load %13 : !llvm.ptr -> i64
%30 = arith.constant 1 : i32
%32 = arith.extsi %30 : i32 to i64
%31 = arith.addi %29, %32 : i64
llvm.store %31, %13 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
cf.br ^bb6
^bb6:
%33 = llvm.load %13 : !llvm.ptr -> i64
%34 = llvm.load %13 : !llvm.ptr -> i64
%35 = arith.muli %33, %34 : i64
%36 = llvm.load %13 : !llvm.ptr -> i64
%37 = arith.muli %35, %36 : i64
%38 = arith.cmpi sgt, %37, %arg0 : i64
cf.cond_br %38, ^bb7, ^bb8
^bb7:
%39 = llvm.load %13 : !llvm.ptr -> i64
%40 = arith.constant 1 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.subi %39, %42 : i64
llvm.store %41, %13 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%43 = llvm.load %13 : !llvm.ptr -> i64
func.return %43 : i64
}
func.func @iroot4(%arg0: i64) -> i64 {
%44 = arith.sitofp %arg0 : i64 to f64
%45 = math.sqrt %44 : f64
%46 = math.sqrt %45 : f64
%47 = arith.fptosi %46 : f64 to i64
%48 = llvm.mlir.constant(1 : i64) : i64
%49 = llvm.alloca %48 x i64 : (i64) -> !llvm.ptr
llvm.store %47, %49 : i64, !llvm.ptr
%50 = arith.extsi %arg0 : i64 to i128
cf.br ^bb9
^bb9:
%51 = llvm.load %49 : !llvm.ptr -> i64
%52 = arith.constant 1 : i32
%54 = arith.extsi %52 : i32 to i64
%53 = arith.addi %51, %54 : i64
%55 = arith.extsi %53 : i64 to i128
%56 = llvm.load %49 : !llvm.ptr -> i64
%57 = arith.constant 1 : i32
%59 = arith.extsi %57 : i32 to i64
%58 = arith.addi %56, %59 : i64
%60 = arith.extsi %58 : i64 to i128
%62 = arith.trunci %55 : i128 to i64
%63 = arith.trunci %60 : i128 to i64
%61 = arith.muli %62, %63 : i64
%64 = llvm.load %49 : !llvm.ptr -> i64
%65 = arith.constant 1 : i32
%67 = arith.extsi %65 : i32 to i64
%66 = arith.addi %64, %67 : i64
%68 = arith.extsi %66 : i64 to i128
%70 = arith.trunci %68 : i128 to i64
%69 = arith.muli %61, %70 : i64
%71 = llvm.load %49 : !llvm.ptr -> i64
%72 = arith.constant 1 : i32
%74 = arith.extsi %72 : i32 to i64
%73 = arith.addi %71, %74 : i64
%75 = arith.extsi %73 : i64 to i128
%77 = arith.trunci %75 : i128 to i64
%76 = arith.muli %69, %77 : i64
%79 = arith.trunci %50 : i128 to i64
%78 = arith.cmpi sle, %76, %79 : i64
cf.cond_br %78, ^bb10, ^bb11
^bb10:
%80 = llvm.load %49 : !llvm.ptr -> i64
%81 = arith.constant 1 : i32
%83 = arith.extsi %81 : i32 to i64
%82 = arith.addi %80, %83 : i64
llvm.store %82, %49 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
cf.br ^bb12
^bb12:
%84 = llvm.load %49 : !llvm.ptr -> i64
%85 = arith.extsi %84 : i64 to i128
%86 = llvm.load %49 : !llvm.ptr -> i64
%87 = arith.extsi %86 : i64 to i128
%89 = arith.trunci %85 : i128 to i64
%90 = arith.trunci %87 : i128 to i64
%88 = arith.muli %89, %90 : i64
%91 = llvm.load %49 : !llvm.ptr -> i64
%92 = arith.extsi %91 : i64 to i128
%94 = arith.trunci %92 : i128 to i64
%93 = arith.muli %88, %94 : i64
%95 = llvm.load %49 : !llvm.ptr -> i64
%96 = arith.extsi %95 : i64 to i128
%98 = arith.trunci %96 : i128 to i64
%97 = arith.muli %93, %98 : i64
%100 = arith.trunci %50 : i128 to i64
%99 = arith.cmpi sgt, %97, %100 : i64
cf.cond_br %99, ^bb13, ^bb14
^bb13:
%101 = llvm.load %49 : !llvm.ptr -> i64
%102 = arith.constant 1 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.subi %101, %104 : i64
llvm.store %103, %49 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%105 = llvm.load %49 : !llvm.ptr -> i64
func.return %105 : i64
}
func.func @isqrt_ll(%arg0: i64) -> i64 {
%106 = arith.constant 0 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.cmpi slt, %arg0, %108 : i64
cf.cond_br %107, ^bb15, ^bb16
^bb15:
%109 = arith.constant 0 : i32
%110 = arith.extsi %109 : i32 to i64
func.return %110 : i64
^bb16:
cf.br ^bb17
^bb17:
%111 = arith.sitofp %arg0 : i64 to f64
%112 = math.sqrt %111 : f64
%113 = arith.fptosi %112 : f64 to i64
%114 = llvm.mlir.constant(1 : i64) : i64
%115 = llvm.alloca %114 x i64 : (i64) -> !llvm.ptr
llvm.store %113, %115 : i64, !llvm.ptr
cf.br ^bb18
^bb18:
%116 = llvm.load %115 : !llvm.ptr -> i64
%117 = arith.constant 1 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.addi %116, %119 : i64
%120 = llvm.load %115 : !llvm.ptr -> i64
%121 = arith.constant 1 : i32
%123 = arith.extsi %121 : i32 to i64
%122 = arith.addi %120, %123 : i64
%124 = arith.muli %118, %122 : i64
%125 = arith.cmpi sle, %124, %arg0 : i64
cf.cond_br %125, ^bb19, ^bb20
^bb19:
%126 = llvm.load %115 : !llvm.ptr -> i64
%127 = arith.constant 1 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.addi %126, %129 : i64
llvm.store %128, %115 : i64, !llvm.ptr
cf.br ^bb18
^bb20:
cf.br ^bb21
^bb21:
%130 = llvm.load %115 : !llvm.ptr -> i64
%131 = llvm.load %115 : !llvm.ptr -> i64
%132 = arith.muli %130, %131 : i64
%133 = arith.cmpi sgt, %132, %arg0 : i64
cf.cond_br %133, ^bb22, ^bb23
^bb22:
%134 = llvm.load %115 : !llvm.ptr -> i64
%135 = arith.constant 1 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.subi %134, %137 : i64
llvm.store %136, %115 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%138 = llvm.load %115 : !llvm.ptr -> i64
func.return %138 : i64
}
func.func @gcd_int(%arg0: i32, %arg1: i32) -> i32 {
%139 = llvm.mlir.constant(1 : i64) : i64
%140 = llvm.alloca %139 x i32 : (i64) -> !llvm.ptr
llvm.store %arg0, %140 : i32, !llvm.ptr
%141 = llvm.mlir.constant(1 : i64) : i64
%142 = llvm.alloca %141 x i32 : (i64) -> !llvm.ptr
llvm.store %arg1, %142 : i32, !llvm.ptr
cf.br ^bb24
^bb24:
%143 = llvm.load %142 : !llvm.ptr -> i32
%144 = arith.constant 0 : i32
%145 = arith.cmpi ne, %143, %144 : i32
cf.cond_br %145, ^bb25, ^bb26
^bb25:
%146 = llvm.load %140 : !llvm.ptr -> i32
%147 = llvm.load %142 : !llvm.ptr -> i32
%148 = arith.remsi %146, %147 : i32
%149 = llvm.load %142 : !llvm.ptr -> i32
llvm.store %149, %140 : i32, !llvm.ptr
llvm.store %148, %142 : i32, !llvm.ptr
cf.br ^bb24
^bb26:
%150 = llvm.load %140 : !llvm.ptr -> i32
func.return %150 : i32
}
func.func @build_spf(%arg0: i32) -> () {
%152 = arith.constant 1 : i32
%153 = arith.addi %arg0, %152 : i32
%154 = arith.extsi %153 : i32 to i64
%155 = arith.constant 4 : i32
%156 = arith.extsi %155 : i32 to i64
%151 = func.call @calloc(%154, %156) : (i64, i64) -> !llvm.ptr
%157 = llvm.mlir.addressof @g_spf : !llvm.ptr
llvm.store %151, %157 : !llvm.ptr, !llvm.ptr
%158 = arith.constant 0 : i32
%159 = llvm.mlir.constant(1 : i64) : i64
%160 = llvm.alloca %159 x i32 : (i64) -> !llvm.ptr
llvm.store %158, %160 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%161 = llvm.load %160 : !llvm.ptr -> i32
%162 = arith.cmpi sle, %161, %arg0 : i32
cf.cond_br %162, ^bb28, ^bb29
^bb28:
%163 = llvm.load %160 : !llvm.ptr -> i32
%164 = llvm.mlir.addressof @g_spf : !llvm.ptr
%165 = llvm.load %164 : !llvm.ptr -> !llvm.ptr
%166 = llvm.load %160 : !llvm.ptr -> i32
%167 = arith.extsi %166 : i32 to i64
%168 = llvm.getelementptr %165[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %163, %168 : i32, !llvm.ptr
%169 = llvm.load %160 : !llvm.ptr -> i32
%170 = arith.constant 1 : i32
%171 = arith.addi %169, %170 : i32
llvm.store %171, %160 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%172 = arith.constant 1 : i32
%173 = llvm.mlir.addressof @g_spf : !llvm.ptr
%174 = llvm.load %173 : !llvm.ptr -> !llvm.ptr
%175 = arith.constant 1 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.getelementptr %174[%176] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %172, %177 : i32, !llvm.ptr
%178 = arith.constant 2 : i32
%179 = llvm.mlir.constant(1 : i64) : i64
%180 = llvm.alloca %179 x i32 : (i64) -> !llvm.ptr
llvm.store %178, %180 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%181 = llvm.load %180 : !llvm.ptr -> i32
%182 = arith.extsi %181 : i32 to i64
%183 = llvm.load %180 : !llvm.ptr -> i32
%184 = arith.extsi %183 : i32 to i64
%185 = arith.muli %182, %184 : i64
%186 = arith.extsi %arg0 : i32 to i64
%187 = arith.cmpi sle, %185, %186 : i64
cf.cond_br %187, ^bb31, ^bb32
^bb31:
%189 = llvm.mlir.addressof @g_spf : !llvm.ptr
%190 = llvm.load %189 : !llvm.ptr -> !llvm.ptr
%191 = llvm.load %180 : !llvm.ptr -> i32
%192 = arith.extsi %191 : i32 to i64
%193 = llvm.getelementptr %190[%192] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%188 = llvm.load %193 : !llvm.ptr -> i32
%194 = llvm.load %180 : !llvm.ptr -> i32
%195 = arith.cmpi eq, %188, %194 : i32
cf.cond_br %195, ^bb33, ^bb34
^bb33:
%196 = llvm.load %180 : !llvm.ptr -> i32
%197 = llvm.load %180 : !llvm.ptr -> i32
%198 = arith.muli %196, %197 : i32
%199 = llvm.mlir.constant(1 : i64) : i64
%200 = llvm.alloca %199 x i32 : (i64) -> !llvm.ptr
llvm.store %198, %200 : i32, !llvm.ptr
cf.br ^bb36
^bb36:
%201 = llvm.load %200 : !llvm.ptr -> i32
%202 = arith.cmpi sle, %201, %arg0 : i32
cf.cond_br %202, ^bb37, ^bb38
^bb37:
%204 = llvm.mlir.addressof @g_spf : !llvm.ptr
%205 = llvm.load %204 : !llvm.ptr -> !llvm.ptr
%206 = llvm.load %200 : !llvm.ptr -> i32
%207 = arith.extsi %206 : i32 to i64
%208 = llvm.getelementptr %205[%207] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%203 = llvm.load %208 : !llvm.ptr -> i32
%209 = llvm.load %200 : !llvm.ptr -> i32
%210 = arith.cmpi eq, %203, %209 : i32
cf.cond_br %210, ^bb39, ^bb40
^bb39:
%211 = llvm.load %180 : !llvm.ptr -> i32
%212 = llvm.mlir.addressof @g_spf : !llvm.ptr
%213 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
%214 = llvm.load %200 : !llvm.ptr -> i32
%215 = arith.extsi %214 : i32 to i64
%216 = llvm.getelementptr %213[%215] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %211, %216 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%217 = llvm.load %200 : !llvm.ptr -> i32
%218 = llvm.load %180 : !llvm.ptr -> i32
%219 = arith.addi %217, %218 : i32
llvm.store %219, %200 : i32, !llvm.ptr
cf.br ^bb36
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%220 = llvm.load %180 : !llvm.ptr -> i32
%221 = arith.constant 1 : i32
%222 = arith.addi %220, %221 : i32
llvm.store %222, %180 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
func.return
}
func.func @cube_free_table(%arg0: i32) -> !llvm.ptr {
func.call @build_spf(%arg0) : (i32) -> ()
%225 = arith.constant 1 : i32
%226 = arith.addi %arg0, %225 : i32
%227 = arith.extsi %226 : i32 to i64
%228 = arith.constant 4 : i32
%229 = arith.extsi %228 : i32 to i64
%224 = func.call @calloc(%227, %229) : (i64, i64) -> !llvm.ptr
%230 = arith.constant 1 : i32
%231 = arith.constant 0 : i32
%232 = arith.extsi %231 : i32 to i64
%233 = llvm.getelementptr %224[%232] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %230, %233 : i32, !llvm.ptr
%234 = arith.constant 1 : i32
%235 = arith.constant 1 : i32
%236 = arith.extsi %235 : i32 to i64
%237 = llvm.getelementptr %224[%236] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %234, %237 : i32, !llvm.ptr
%238 = arith.constant 2 : i32
%239 = llvm.mlir.constant(1 : i64) : i64
%240 = llvm.alloca %239 x i32 : (i64) -> !llvm.ptr
llvm.store %238, %240 : i32, !llvm.ptr
cf.br ^bb42
^bb42:
%241 = llvm.load %240 : !llvm.ptr -> i32
%242 = arith.cmpi sle, %241, %arg0 : i32
cf.cond_br %242, ^bb43, ^bb44
^bb43:
%244 = llvm.mlir.addressof @g_spf : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> !llvm.ptr
%246 = llvm.load %240 : !llvm.ptr -> i32
%247 = arith.extsi %246 : i32 to i64
%248 = llvm.getelementptr %245[%247] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%243 = llvm.load %248 : !llvm.ptr -> i32
%249 = llvm.load %240 : !llvm.ptr -> i32
%250 = arith.divsi %249, %243 : i32
%251 = llvm.mlir.constant(1 : i64) : i64
%252 = llvm.alloca %251 x i32 : (i64) -> !llvm.ptr
llvm.store %250, %252 : i32, !llvm.ptr
%253 = arith.constant 1 : i32
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x i32 : (i64) -> !llvm.ptr
llvm.store %253, %255 : i32, !llvm.ptr
cf.br ^bb45
^bb45:
%256 = llvm.load %252 : !llvm.ptr -> i32
%257 = arith.remsi %256, %243 : i32
%258 = arith.constant 0 : i32
%259 = arith.cmpi eq, %257, %258 : i32
cf.cond_br %259, ^bb46, ^bb47
^bb46:
%260 = llvm.load %252 : !llvm.ptr -> i32
%261 = arith.divsi %260, %243 : i32
llvm.store %261, %252 : i32, !llvm.ptr
%262 = llvm.load %255 : !llvm.ptr -> i32
%263 = arith.constant 1 : i32
%264 = arith.addi %262, %263 : i32
llvm.store %264, %255 : i32, !llvm.ptr
cf.br ^bb45
^bb47:
%265 = llvm.load %255 : !llvm.ptr -> i32
%266 = arith.constant 3 : i32
%267 = arith.remsi %265, %266 : i32
%268 = arith.constant 0 : i32
%269 = arith.cmpi eq, %267, %268 : i32
cf.cond_br %269, ^bb48, ^bb49
^bb48:
%271 = llvm.load %252 : !llvm.ptr -> i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %224[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%270 = llvm.load %273 : !llvm.ptr -> i32
%274 = llvm.load %240 : !llvm.ptr -> i32
%275 = arith.extsi %274 : i32 to i64
%276 = llvm.getelementptr %224[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %270, %276 : i32, !llvm.ptr
cf.br ^bb50
^bb49:
%277 = arith.constant 1 : i32
%278 = arith.cmpi eq, %267, %277 : i32
cf.cond_br %278, ^bb51, ^bb52
^bb51:
%280 = llvm.load %252 : !llvm.ptr -> i32
%281 = arith.extsi %280 : i32 to i64
%282 = llvm.getelementptr %224[%281] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%279 = llvm.load %282 : !llvm.ptr -> i32
%283 = arith.muli %279, %243 : i32
%284 = llvm.load %240 : !llvm.ptr -> i32
%285 = arith.extsi %284 : i32 to i64
%286 = llvm.getelementptr %224[%285] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %283, %286 : i32, !llvm.ptr
cf.br ^bb53
^bb52:
%288 = llvm.load %252 : !llvm.ptr -> i32
%289 = arith.extsi %288 : i32 to i64
%290 = llvm.getelementptr %224[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%287 = llvm.load %290 : !llvm.ptr -> i32
%291 = arith.muli %287, %243 : i32
%292 = arith.muli %291, %243 : i32
%293 = llvm.load %240 : !llvm.ptr -> i32
%294 = arith.extsi %293 : i32 to i64
%295 = llvm.getelementptr %224[%294] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %292, %295 : i32, !llvm.ptr
cf.br ^bb53
^bb53:
cf.br ^bb50
^bb50:
%296 = llvm.load %240 : !llvm.ptr -> i32
%297 = arith.constant 1 : i32
%298 = arith.addi %296, %297 : i32
llvm.store %298, %240 : i32, !llvm.ptr
cf.br ^bb42
^bb44:
func.return %224 : !llvm.ptr
}
func.func @sumsq_mod(%arg0: i64, %arg1: i64) -> i64 {
%299 = arith.extsi %arg0 : i64 to i128
%300 = arith.constant 1 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.addi %arg0, %302 : i64
%303 = arith.extsi %301 : i64 to i128
%305 = arith.trunci %299 : i128 to i64
%306 = arith.trunci %303 : i128 to i64
%304 = arith.muli %305, %306 : i64
%307 = arith.constant 2 : i32
%309 = arith.extsi %307 : i32 to i64
%308 = arith.muli %309, %arg0 : i64
%310 = arith.constant 1 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.addi %308, %312 : i64
%313 = arith.extsi %311 : i64 to i128
%315 = arith.trunci %313 : i128 to i64
%314 = arith.muli %304, %315 : i64
%316 = arith.constant 6 : i32
%318 = arith.extsi %316 : i32 to i64
%317 = arith.divsi %314, %318 : i64
%319 = arith.extsi %317 : i64 to i128
%320 = arith.extsi %arg1 : i64 to i128
%322 = arith.trunci %319 : i128 to i64
%323 = arith.trunci %320 : i128 to i64
%321 = arith.remsi %322, %323 : i64
func.return %321 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%324 = arith.extsi %arg0 : i64 to i128
%325 = arith.extsi %arg1 : i64 to i128
%326 = arith.extsi %arg2 : i64 to i128
%328 = arith.trunci %324 : i128 to i64
%329 = arith.trunci %325 : i128 to i64
%327 = arith.muli %328, %329 : i64
%331 = arith.trunci %326 : i128 to i64
%330 = arith.remsi %327, %331 : i64
%332 = arith.extsi %330 : i64 to i128
%333 = arith.trunci %332 : i128 to i64
func.return %333 : i64
}
func.func @H_mod(%arg0: i64) -> i64 {
%335 = arith.constant 4 : i32
%337 = arith.extsi %335 : i32 to i64
%336 = arith.muli %337, %arg0 : i64
%334 = func.call @iroot4(%336) : (i64) -> i64
%338 = arith.constant 0 : i32
%339 = arith.extsi %338 : i32 to i64
%340 = llvm.mlir.constant(1 : i64) : i64
%341 = llvm.alloca %340 x i64 : (i64) -> !llvm.ptr
llvm.store %339, %341 : i64, !llvm.ptr
%342 = func.call @icbrt(%arg0) : (i64) -> i64
%343 = arith.constant 1 : i32
%345 = arith.extsi %343 : i32 to i64
%344 = arith.cmpi sgt, %342, %345 : i64
cf.cond_br %344, ^bb54, ^bb55
^bb54:
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.subi %342, %348 : i64
%349 = arith.constant 4 : i32
%351 = arith.extsi %349 : i32 to i64
%350 = arith.divsi %347, %351 : i64
llvm.store %350, %341 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%352 = arith.constant 0 : i32
%353 = arith.extsi %352 : i32 to i64
%354 = llvm.mlir.constant(1 : i64) : i64
%355 = llvm.alloca %354 x i64 : (i64) -> !llvm.ptr
llvm.store %353, %355 : i64, !llvm.ptr
%357 = arith.constant 4 : i32
%359 = arith.extsi %357 : i32 to i64
%358 = arith.divsi %arg0, %359 : i64
%356 = func.call @icbrt(%358) : (i64) -> i64
%360 = arith.constant 1 : i32
%362 = arith.extsi %360 : i32 to i64
%361 = arith.cmpi sgt, %356, %362 : i64
cf.cond_br %361, ^bb57, ^bb58
^bb57:
%363 = arith.constant 1 : i32
%365 = arith.extsi %363 : i32 to i64
%364 = arith.subi %356, %365 : i64
%366 = arith.constant 2 : i32
%368 = arith.extsi %366 : i32 to i64
%367 = arith.divsi %364, %368 : i64
llvm.store %367, %355 : i64, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%369 = arith.constant 4 : i32
%370 = llvm.load %341 : !llvm.ptr -> i64
%372 = arith.extsi %369 : i32 to i64
%371 = arith.muli %372, %370 : i64
%373 = llvm.mlir.constant(1 : i64) : i64
%374 = llvm.alloca %373 x i64 : (i64) -> !llvm.ptr
llvm.store %371, %374 : i64, !llvm.ptr
%375 = llvm.load %355 : !llvm.ptr -> i64
%376 = llvm.load %374 : !llvm.ptr -> i64
%377 = arith.cmpi sgt, %375, %376 : i64
cf.cond_br %377, ^bb60, ^bb61
^bb60:
%378 = llvm.load %355 : !llvm.ptr -> i64
llvm.store %378, %374 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%379 = arith.constant 2 : i32
%381 = arith.extsi %379 : i32 to i64
%380 = arith.muli %381, %334 : i64
%382 = llvm.load %374 : !llvm.ptr -> i64
%383 = arith.cmpi sgt, %380, %382 : i64
cf.cond_br %383, ^bb63, ^bb64
^bb63:
%384 = arith.constant 2 : i32
%386 = arith.extsi %384 : i32 to i64
%385 = arith.muli %386, %334 : i64
llvm.store %385, %374 : i64, !llvm.ptr
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
%387 = llvm.load %374 : !llvm.ptr -> i64
%388 = arith.trunci %387 : i64 to i32
%389 = func.call @cube_free_table(%388) : (i32) -> !llvm.ptr
%391 = llvm.load %341 : !llvm.ptr -> i64
%392 = arith.constant 1 : i32
%394 = arith.extsi %392 : i32 to i64
%393 = arith.addi %391, %394 : i64
%395 = arith.constant 4 : i32
%396 = arith.extsi %395 : i32 to i64
%390 = func.call @calloc(%393, %396) : (i64, i64) -> !llvm.ptr
%397 = arith.constant 0 : i32
%398 = arith.constant 0 : i32
%399 = arith.extsi %398 : i32 to i64
%400 = llvm.getelementptr %390[%399] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %397, %400 : i32, !llvm.ptr
%401 = arith.constant 1 : i32
%402 = arith.extsi %401 : i32 to i64
%403 = llvm.mlir.constant(1 : i64) : i64
%404 = llvm.alloca %403 x i64 : (i64) -> !llvm.ptr
llvm.store %402, %404 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%405 = llvm.load %404 : !llvm.ptr -> i64
%406 = llvm.load %341 : !llvm.ptr -> i64
%407 = arith.cmpi sle, %405, %406 : i64
cf.cond_br %407, ^bb67, ^bb68
^bb67:
%409 = arith.constant 4 : i32
%410 = llvm.load %404 : !llvm.ptr -> i64
%412 = arith.extsi %409 : i32 to i64
%411 = arith.muli %412, %410 : i64
%413 = llvm.getelementptr %389[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%408 = llvm.load %413 : !llvm.ptr -> i32
%414 = llvm.load %404 : !llvm.ptr -> i64
%415 = llvm.getelementptr %390[%414] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %408, %415 : i32, !llvm.ptr
%416 = llvm.load %404 : !llvm.ptr -> i64
%417 = arith.constant 1 : i32
%419 = arith.extsi %417 : i32 to i64
%418 = arith.addi %416, %419 : i64
llvm.store %418, %404 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%420 = arith.constant 0 : i32
%421 = arith.extsi %420 : i32 to i64
%422 = llvm.mlir.constant(1 : i64) : i64
%423 = llvm.alloca %422 x i64 : (i64) -> !llvm.ptr
llvm.store %421, %423 : i64, !llvm.ptr
%424 = llvm.mlir.addressof @MOD : !llvm.ptr
%425 = llvm.load %424 : !llvm.ptr -> i64
%426 = arith.constant 1 : i32
%427 = arith.extsi %426 : i32 to i64
%428 = llvm.mlir.constant(1 : i64) : i64
%429 = llvm.alloca %428 x i64 : (i64) -> !llvm.ptr
llvm.store %427, %429 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%430 = llvm.load %429 : !llvm.ptr -> i64
%431 = arith.cmpi sle, %430, %334 : i64
cf.cond_br %431, ^bb70, ^bb71
^bb70:
%433 = llvm.load %429 : !llvm.ptr -> i64
%434 = arith.divsi %arg0, %433 : i64
%432 = func.call @icbrt(%434) : (i64) -> i64
%435 = llvm.load %429 : !llvm.ptr -> i64
%436 = arith.subi %432, %435 : i64
%437 = arith.constant 4 : i32
%439 = arith.extsi %437 : i32 to i64
%438 = arith.divsi %436, %439 : i64
%441 = llvm.load %429 : !llvm.ptr -> i64
%442 = llvm.getelementptr %389[%441] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%440 = llvm.load %442 : !llvm.ptr -> i32
%443 = arith.constant 1 : i32
%444 = arith.extsi %443 : i32 to i64
%445 = llvm.mlir.constant(1 : i64) : i64
%446 = llvm.alloca %445 x i64 : (i64) -> !llvm.ptr
llvm.store %444, %446 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%447 = llvm.load %446 : !llvm.ptr -> i64
%448 = arith.cmpi sle, %447, %438 : i64
cf.cond_br %448, ^bb73, ^bb74
^bb73:
%450 = llvm.load %446 : !llvm.ptr -> i64
%451 = arith.trunci %450 : i64 to i32
%452 = llvm.load %429 : !llvm.ptr -> i64
%453 = arith.trunci %452 : i64 to i32
%449 = func.call @gcd_int(%451, %453) : (i32, i32) -> i32
%454 = arith.constant 1 : i32
%455 = arith.cmpi eq, %449, %454 : i32
%456 = scf.if %455 -> (i1) {
%458 = llvm.load %446 : !llvm.ptr -> i64
%459 = llvm.getelementptr %390[%458] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%457 = llvm.load %459 : !llvm.ptr -> i32
%460 = arith.cmpi ne, %440, %457 : i32
scf.yield %460 : i1
} else {
%461 = arith.constant false
scf.yield %461 : i1
}
cf.cond_br %456, ^bb75, ^bb76
^bb75:
%462 = llvm.load %429 : !llvm.ptr -> i64
%463 = arith.constant 4 : i32
%464 = llvm.load %446 : !llvm.ptr -> i64
%466 = arith.extsi %463 : i32 to i64
%465 = arith.muli %466, %464 : i64
%467 = arith.addi %462, %465 : i64
%468 = llvm.load %429 : !llvm.ptr -> i64
%469 = arith.extsi %468 : i64 to i128
%470 = arith.extsi %467 : i64 to i128
%472 = arith.trunci %469 : i128 to i64
%473 = arith.trunci %470 : i128 to i64
%471 = arith.muli %472, %473 : i64
%474 = arith.extsi %467 : i64 to i128
%476 = arith.trunci %474 : i128 to i64
%475 = arith.muli %471, %476 : i64
%477 = arith.extsi %467 : i64 to i128
%479 = arith.trunci %477 : i128 to i64
%478 = arith.muli %475, %479 : i64
%480 = arith.extsi %478 : i64 to i128
%481 = llvm.load %446 : !llvm.ptr -> i64
%482 = arith.constant 2 : i32
%483 = llvm.load %429 : !llvm.ptr -> i64
%485 = arith.extsi %482 : i32 to i64
%484 = arith.muli %485, %483 : i64
%486 = arith.subi %481, %484 : i64
%487 = arith.extsi %486 : i64 to i128
%488 = arith.extsi %486 : i64 to i128
%490 = arith.trunci %487 : i128 to i64
%491 = arith.trunci %488 : i128 to i64
%489 = arith.muli %490, %491 : i64
%492 = arith.extsi %486 : i64 to i128
%494 = arith.trunci %492 : i128 to i64
%493 = arith.muli %489, %494 : i64
%495 = arith.extsi %493 : i64 to i128
%496 = llvm.mlir.constant(1 : i64) : i64
%497 = llvm.alloca %496 x i128 : (i64) -> !llvm.ptr
llvm.store %495, %497 : i128, !llvm.ptr
%498 = llvm.load %497 : !llvm.ptr -> i128
%499 = arith.constant 0 : i32
%501 = arith.trunci %498 : i128 to i64
%502 = arith.extsi %499 : i32 to i64
%500 = arith.cmpi slt, %501, %502 : i64
cf.cond_br %500, ^bb78, ^bb79
^bb78:
%503 = arith.constant 0 : i32
%504 = llvm.load %497 : !llvm.ptr -> i128
%506 = arith.extsi %503 : i32 to i64
%507 = arith.trunci %504 : i128 to i64
%505 = arith.subi %506, %507 : i64
%508 = arith.extsi %505 : i64 to i128
llvm.store %508, %497 : i128, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%509 = arith.constant 4 : i32
%510 = llvm.load %446 : !llvm.ptr -> i64
%511 = arith.extsi %510 : i64 to i128
%513 = arith.extsi %509 : i32 to i64
%514 = arith.trunci %511 : i128 to i64
%512 = arith.muli %513, %514 : i64
%515 = llvm.load %497 : !llvm.ptr -> i128
%517 = arith.trunci %515 : i128 to i64
%516 = arith.muli %512, %517 : i64
%518 = arith.extsi %516 : i64 to i128
%519 = llvm.mlir.constant(1 : i64) : i64
%520 = llvm.alloca %519 x i128 : (i64) -> !llvm.ptr
llvm.store %480, %520 : i128, !llvm.ptr
%522 = arith.trunci %518 : i128 to i64
%523 = arith.trunci %480 : i128 to i64
%521 = arith.cmpi sgt, %522, %523 : i64
cf.cond_br %521, ^bb81, ^bb82
^bb81:
llvm.store %518, %520 : i128, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%524 = llvm.load %520 : !llvm.ptr -> i128
%525 = arith.extsi %arg0 : i64 to i128
%527 = arith.trunci %524 : i128 to i64
%528 = arith.trunci %525 : i128 to i64
%526 = arith.cmpi sle, %527, %528 : i64
cf.cond_br %526, ^bb84, ^bb85
^bb84:
%529 = llvm.load %520 : !llvm.ptr -> i128
%530 = arith.trunci %529 : i128 to i64
%532 = arith.divsi %arg0, %530 : i64
%531 = func.call @isqrt_ll(%532) : (i64) -> i64
%533 = func.call @sumsq_mod(%531, %425) : (i64, i64) -> i64
%535 = arith.trunci %480 : i128 to i64
%536 = arith.trunci %518 : i128 to i64
%534 = arith.addi %535, %536 : i64
%537 = arith.extsi %425 : i64 to i128
%539 = arith.trunci %537 : i128 to i64
%538 = arith.remsi %534, %539 : i64
%540 = func.call @mulmod(%538, %533, %425) : (i64, i64, i64) -> i64
%541 = llvm.load %423 : !llvm.ptr -> i64
%542 = arith.addi %541, %540 : i64
%543 = arith.remsi %542, %425 : i64
llvm.store %543, %423 : i64, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
%544 = llvm.load %446 : !llvm.ptr -> i64
%545 = arith.constant 1 : i32
%547 = arith.extsi %545 : i32 to i64
%546 = arith.addi %544, %547 : i64
llvm.store %546, %446 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%548 = llvm.load %429 : !llvm.ptr -> i64
%549 = arith.constant 2 : i32
%551 = arith.extsi %549 : i32 to i64
%550 = arith.addi %548, %551 : i64
llvm.store %550, %429 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%552 = arith.constant 2 : i32
%553 = arith.extsi %552 : i32 to i64
llvm.store %553, %429 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%554 = llvm.load %429 : !llvm.ptr -> i64
%555 = arith.cmpi sle, %554, %334 : i64
cf.cond_br %555, ^bb88, ^bb89
^bb88:
%556 = llvm.load %429 : !llvm.ptr -> i64
%557 = arith.constant 2 : i32
%559 = arith.extsi %557 : i32 to i64
%558 = arith.divsi %556, %559 : i64
%561 = arith.constant 2 : i32
%562 = llvm.load %429 : !llvm.ptr -> i64
%564 = arith.extsi %561 : i32 to i64
%563 = arith.muli %564, %562 : i64
%565 = arith.divsi %arg0, %563 : i64
%560 = func.call @icbrt(%565) : (i64) -> i64
%566 = arith.subi %560, %558 : i64
%567 = arith.constant 2 : i32
%569 = arith.extsi %567 : i32 to i64
%568 = arith.divsi %566, %569 : i64
%571 = arith.constant 2 : i32
%572 = llvm.load %429 : !llvm.ptr -> i64
%574 = arith.extsi %571 : i32 to i64
%573 = arith.muli %574, %572 : i64
%575 = llvm.getelementptr %389[%573] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%570 = llvm.load %575 : !llvm.ptr -> i32
%576 = arith.constant 1 : i32
%577 = arith.extsi %576 : i32 to i64
%578 = llvm.mlir.constant(1 : i64) : i64
%579 = llvm.alloca %578 x i64 : (i64) -> !llvm.ptr
llvm.store %577, %579 : i64, !llvm.ptr
cf.br ^bb90
^bb90:
%580 = llvm.load %579 : !llvm.ptr -> i64
%581 = arith.cmpi sle, %580, %568 : i64
cf.cond_br %581, ^bb91, ^bb92
^bb91:
%583 = llvm.load %579 : !llvm.ptr -> i64
%584 = arith.trunci %583 : i64 to i32
%585 = llvm.load %429 : !llvm.ptr -> i64
%586 = arith.trunci %585 : i64 to i32
%582 = func.call @gcd_int(%584, %586) : (i32, i32) -> i32
%587 = arith.constant 1 : i32
%588 = arith.cmpi eq, %582, %587 : i32
%589 = scf.if %588 -> (i1) {
%591 = llvm.load %579 : !llvm.ptr -> i64
%592 = llvm.getelementptr %389[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%590 = llvm.load %592 : !llvm.ptr -> i32
%593 = arith.cmpi ne, %570, %590 : i32
scf.yield %593 : i1
} else {
%594 = arith.constant false
scf.yield %594 : i1
}
cf.cond_br %589, ^bb93, ^bb94
^bb93:
%595 = arith.constant 2 : i32
%596 = llvm.load %579 : !llvm.ptr -> i64
%598 = arith.extsi %595 : i32 to i64
%597 = arith.muli %598, %596 : i64
%599 = arith.addi %558, %597 : i64
%600 = arith.constant 2 : i32
%601 = arith.extsi %600 : i32 to i128
%602 = llvm.load %429 : !llvm.ptr -> i64
%603 = arith.extsi %602 : i64 to i128
%605 = arith.trunci %601 : i128 to i64
%606 = arith.trunci %603 : i128 to i64
%604 = arith.muli %605, %606 : i64
%607 = arith.extsi %599 : i64 to i128
%609 = arith.trunci %607 : i128 to i64
%608 = arith.muli %604, %609 : i64
%610 = arith.extsi %599 : i64 to i128
%612 = arith.trunci %610 : i128 to i64
%611 = arith.muli %608, %612 : i64
%613 = arith.extsi %599 : i64 to i128
%615 = arith.trunci %613 : i128 to i64
%614 = arith.muli %611, %615 : i64
%616 = arith.extsi %614 : i64 to i128
%617 = llvm.load %579 : !llvm.ptr -> i64
%618 = arith.constant 2 : i32
%619 = llvm.load %429 : !llvm.ptr -> i64
%621 = arith.extsi %618 : i32 to i64
%620 = arith.muli %621, %619 : i64
%622 = arith.subi %617, %620 : i64
%623 = arith.extsi %622 : i64 to i128
%624 = arith.extsi %622 : i64 to i128
%626 = arith.trunci %623 : i128 to i64
%627 = arith.trunci %624 : i128 to i64
%625 = arith.muli %626, %627 : i64
%628 = arith.extsi %622 : i64 to i128
%630 = arith.trunci %628 : i128 to i64
%629 = arith.muli %625, %630 : i64
%631 = arith.extsi %629 : i64 to i128
%632 = llvm.mlir.constant(1 : i64) : i64
%633 = llvm.alloca %632 x i128 : (i64) -> !llvm.ptr
llvm.store %631, %633 : i128, !llvm.ptr
%634 = llvm.load %633 : !llvm.ptr -> i128
%635 = arith.constant 0 : i32
%637 = arith.trunci %634 : i128 to i64
%638 = arith.extsi %635 : i32 to i64
%636 = arith.cmpi slt, %637, %638 : i64
cf.cond_br %636, ^bb96, ^bb97
^bb96:
%639 = arith.constant 0 : i32
%640 = llvm.load %633 : !llvm.ptr -> i128
%642 = arith.extsi %639 : i32 to i64
%643 = arith.trunci %640 : i128 to i64
%641 = arith.subi %642, %643 : i64
%644 = arith.extsi %641 : i64 to i128
llvm.store %644, %633 : i128, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%645 = llvm.load %579 : !llvm.ptr -> i64
%646 = arith.extsi %645 : i64 to i128
%647 = llvm.load %633 : !llvm.ptr -> i128
%649 = arith.trunci %646 : i128 to i64
%650 = arith.trunci %647 : i128 to i64
%648 = arith.muli %649, %650 : i64
%651 = arith.extsi %648 : i64 to i128
%652 = llvm.mlir.constant(1 : i64) : i64
%653 = llvm.alloca %652 x i128 : (i64) -> !llvm.ptr
llvm.store %616, %653 : i128, !llvm.ptr
%655 = arith.trunci %651 : i128 to i64
%656 = arith.trunci %616 : i128 to i64
%654 = arith.cmpi sgt, %655, %656 : i64
cf.cond_br %654, ^bb99, ^bb100
^bb99:
llvm.store %651, %653 : i128, !llvm.ptr
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%657 = llvm.load %653 : !llvm.ptr -> i128
%658 = arith.extsi %arg0 : i64 to i128
%660 = arith.trunci %657 : i128 to i64
%661 = arith.trunci %658 : i128 to i64
%659 = arith.cmpi sle, %660, %661 : i64
cf.cond_br %659, ^bb102, ^bb103
^bb102:
%662 = llvm.load %653 : !llvm.ptr -> i128
%663 = arith.trunci %662 : i128 to i64
%665 = arith.divsi %arg0, %663 : i64
%664 = func.call @isqrt_ll(%665) : (i64) -> i64
%666 = func.call @sumsq_mod(%664, %425) : (i64, i64) -> i64
%668 = arith.trunci %616 : i128 to i64
%669 = arith.trunci %651 : i128 to i64
%667 = arith.addi %668, %669 : i64
%670 = arith.extsi %425 : i64 to i128
%672 = arith.trunci %670 : i128 to i64
%671 = arith.remsi %667, %672 : i64
%673 = func.call @mulmod(%671, %666, %425) : (i64, i64, i64) -> i64
%674 = llvm.load %423 : !llvm.ptr -> i64
%675 = arith.addi %674, %673 : i64
%676 = arith.remsi %675, %425 : i64
llvm.store %676, %423 : i64, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%677 = llvm.load %579 : !llvm.ptr -> i64
%678 = arith.constant 2 : i32
%680 = arith.extsi %678 : i32 to i64
%679 = arith.addi %677, %680 : i64
llvm.store %679, %579 : i64, !llvm.ptr
cf.br ^bb90
^bb92:
%681 = llvm.load %429 : !llvm.ptr -> i64
%682 = arith.constant 2 : i32
%684 = arith.extsi %682 : i32 to i64
%683 = arith.addi %681, %684 : i64
llvm.store %683, %429 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
func.call @free(%389) : (!llvm.ptr) -> ()
func.call @free(%390) : (!llvm.ptr) -> ()
%688 = llvm.mlir.addressof @g_spf : !llvm.ptr
%689 = llvm.load %688 : !llvm.ptr -> !llvm.ptr
func.call @free(%689) : (!llvm.ptr) -> ()
%690 = llvm.load %423 : !llvm.ptr -> i64
func.return %690 : i64
}
func.func @main() -> i32 {
%692 = llvm.mlir.addressof @N : !llvm.ptr
%693 = llvm.load %692 : !llvm.ptr -> i64
%691 = func.call @H_mod(%693) : (i64) -> i64
%694 = llvm.mlir.addressof @MOD : !llvm.ptr
%695 = llvm.load %694 : !llvm.ptr -> i64
%696 = arith.remsi %691, %695 : i64
%697 = llvm.mlir.addressof @str_0 : !llvm.ptr
%698 = llvm.call @printf(%697, %696) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%699 = arith.constant 0 : i32
func.return %699 : i32
}
}