← All problems Problem 354
Count L <= 5e11 with B(L)=450 on hexagonal lattice (R(n)=75).
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n^2)Space complexity O(n^2)O(n^2)Approach Flow solution Combinatorial or DP counting Verdict Optimal
Flow source
# Project Euler 354
# Count L <= 5e11 with B(L)=450 on hexagonal lattice (R(n)=75).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function isqrt64(n: i64) -> i64 {
if n <= 0 { return 0 }
let mut x: i64 = n
let mut y: i64 = (x + 1) / 2
while y < x {
x = y
y = (x + n / x) / 2
}
return x
}
function isqrt128(n: i128) -> i64 {
if n <= 0 { return 0 }
if n < 9223372036854775807 {
return isqrt64(n as i64)
}
let mut x: i128 = n
let mut y: i128 = (x + 1) / 2
while y < x {
x = y
y = (x + n / x) / 2
}
return x as i64
}
function ipow128(base: i64, exp: i64) -> i128 {
let mut r: i128 = 1
let mut b: i128 = base as i128
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 { r = r * b }
b = b * b
e = e / 2
}
return r
}
function nth_root128(n: i128, k: i64) -> i64 {
if n < 2 { return n as i64 }
if k == 1 {
if n > 9223372036854775807 { return 9223372036854775807 }
return n as i64
}
let mut lo: i64 = 1
let mut hi: i64 = 2
# upper bound
while ipow128(hi, k) <= n {
if hi > 1000000000 { break }
hi = hi * 2
}
if hi > 100000000 { hi = 100000000 }
while lo + 1 < hi {
let mid: i64 = (lo + hi) / 2
if ipow128(mid, k) <= n {
lo = mid
} else {
hi = mid
}
}
return lo
}
function lower_bound(arr: ptr<i32>, n: i64, key: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = n
while lo < hi {
let mid: i64 = (lo + hi) / 2
if (arr[mid] as i64) < key { lo = mid + 1 }
else { hi = mid }
}
return lo
}
function upper_bound(arr: ptr<i32>, n: i64, key: i64) -> i64 {
let mut lo: i64 = 0
let mut hi: i64 = n
while lo < hi {
let mid: i64 = (lo + hi) / 2
if (arr[mid] as i64) <= key { lo = mid + 1 }
else { hi = mid }
}
return lo
}
function main() -> i32 {
let Lmax: i128 = 500000000000
let N: i128 = (Lmax * Lmax) / 3
let base_7_13: i128 = ipow128(7, 4) * ipow128(13, 4)
let max_prime: i64 = isqrt128(N / base_7_13)
let sieve: ptr<i8> = calloc(max_prime + 1, 1)
let primes: ptr<i32> = calloc(max_prime / 5 + 10, 4)
let mut pc: i64 = 0
sieve[0] = 1
sieve[1] = 1
let mut i: i64 = 2
while i <= max_prime {
if sieve[i] == 0 {
primes[pc] = i as i32
pc = pc + 1
let mut j: i64 = i * i
while j <= max_prime {
sieve[j] = 1
j = j + i
}
}
i = i + 1
}
let primes1: ptr<i32> = calloc(pc, 4)
let mut p1c: i64 = 0
i = 0
while i < pc {
let p: i64 = primes[i] as i64
if p % 3 == 1 {
primes1[p1c] = p as i32
p1c = p1c + 1
}
i = i + 1
}
let A_min: i128 = base_7_13 * ipow128(19, 2)
let Bmax: i64 = isqrt128(N / A_min)
let good: ptr<i8> = calloc(Bmax + 1, 1)
i = 1
while i <= Bmax {
good[i] = 1
i = i + 1
}
i = 0
while i < pc {
let p: i64 = primes[i] as i64
if p > Bmax { break }
if p == 3 || p % 3 == 1 {
let mut j: i64 = p
while j <= Bmax {
good[j] = 0
j = j + p
}
}
i = i + 1
}
let prefix_B: ptr<i32> = calloc(Bmax + 1, 4)
let mut s: i64 = 0
i = 1
while i <= Bmax {
if good[i] != 0 { s = s + 1 }
prefix_B[i] = s as i32
i = i + 1
}
let GCAP: i64 = 1 << 22
let gkeys: ptr<i128> = calloc(GCAP, 16)
let gvals: ptr<i64> = calloc(GCAP, 8)
let gused: ptr<i8> = calloc(GCAP, 1)
let mut ans: i64 = 0
# G helper via repeated open addressing
# Pattern (24,2)
let p24: i128 = ipow128(7, 24)
let qmax: i64 = isqrt128(N / p24)
let q_end: i64 = upper_bound(primes1, p1c, qmax)
let mut qi: i64 = 0
while qi < q_end {
let q: i64 = primes1[qi] as i64
if q != 7 {
let A: i128 = p24 * (q as i128) * (q as i128)
let lim: i128 = N / A
let mut h: i64 = (lim % (GCAP as i128)) as i64
if h < 0 { h = 0 - h }
let mut slot: i64 = h
while gused[slot] != 0 && gkeys[slot] != lim {
slot = (slot + 1) & (GCAP - 1)
}
let mut g: i64 = 0
if gused[slot] != 0 {
g = gvals[slot]
} else {
let mut mm: i128 = lim
while mm > 0 {
let r: i64 = isqrt128(mm)
let mut x: i64 = r
if x > Bmax { x = Bmax }
if x > 0 { g = g + (prefix_B[x] as i64) }
mm = mm / 3
}
gused[slot] = 1
gkeys[slot] = lim
gvals[slot] = g
}
ans = ans + g
}
qi = qi + 1
}
# Pattern (14,4)
let mut pi: i64 = 0
while pi < p1c {
let p: i64 = primes1[pi] as i64
let p14: i128 = ipow128(p, 14)
if p14 > N { break }
let max_q: i64 = nth_root128(N / p14, 4)
let qe: i64 = upper_bound(primes1, p1c, max_q)
qi = 0
while qi < qe {
let q: i64 = primes1[qi] as i64
if q != p {
let q4: i128 = ipow128(q, 4)
let lim: i128 = N / (p14 * q4)
let mut h: i64 = (lim % (GCAP as i128)) as i64
if h < 0 { h = 0 - h }
let mut slot: i64 = h
while gused[slot] != 0 && gkeys[slot] != lim {
slot = (slot + 1) & (GCAP - 1)
}
let mut g: i64 = 0
if gused[slot] != 0 {
g = gvals[slot]
} else {
let mut mm: i128 = lim
while mm > 0 {
let r: i64 = isqrt128(mm)
let mut x: i64 = r
if x > Bmax { x = Bmax }
if x > 0 { g = g + (prefix_B[x] as i64) }
mm = mm / 3
}
gused[slot] = 1
gkeys[slot] = lim
gvals[slot] = g
}
ans = ans + g
}
qi = qi + 1
}
pi = pi + 1
}
# Pattern (4,4,2)
let p_max: i64 = nth_root128(N / 49, 8)
let p_end: i64 = upper_bound(primes1, p1c, p_max)
pi = 0
while pi < p_end {
let p: i64 = primes1[pi] as i64
let p4: i128 = ipow128(p, 4)
let rem: i128 = N / (p4 * 49)
if rem == 0 { break }
let qmax2: i64 = nth_root128(rem, 4)
let q_start: i64 = upper_bound(primes1, p1c, p)
let qe2: i64 = upper_bound(primes1, p1c, qmax2)
qi = q_start
while qi < qe2 {
let q: i64 = primes1[qi] as i64
let base: i128 = p4 * ipow128(q, 4)
let C: i128 = N / base
if C > 0 {
let Rmax: i64 = isqrt128(C)
if Rmax >= 7 {
let mut r_low: i64 = 7
while r_low <= Rmax {
let tt: i128 = C / ((r_low as i128) * (r_low as i128))
if tt == 0 { break }
let mut r_high: i64 = isqrt128(C / tt)
if r_high > Rmax { r_high = Rmax }
let mut cnt: i64 = upper_bound(primes1, p1c, r_high) - lower_bound(primes1, p1c, r_low)
if r_low <= p && p <= r_high { cnt = cnt - 1 }
if p != q && r_low <= q && q <= r_high { cnt = cnt - 1 }
if cnt > 0 {
let lim: i128 = tt
let mut h: i64 = (lim % (GCAP as i128)) as i64
if h < 0 { h = 0 - h }
let mut slot: i64 = h
while gused[slot] != 0 && gkeys[slot] != lim {
slot = (slot + 1) & (GCAP - 1)
}
let mut g: i64 = 0
if gused[slot] != 0 {
g = gvals[slot]
} else {
let mut mm: i128 = lim
while mm > 0 {
let r: i64 = isqrt128(mm)
let mut x: i64 = r
if x > Bmax { x = Bmax }
if x > 0 { g = g + (prefix_B[x] as i64) }
mm = mm / 3
}
gused[slot] = 1
gkeys[slot] = lim
gvals[slot] = g
}
ans = ans + cnt * g
}
r_low = r_high + 1
}
}
}
qi = qi + 1
}
pi = pi + 1
}
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 isqrt64_i64(int64_t n);
int64_t isqrt128_i128(__int128 n);
__int128 ipow128_i64_i64(int64_t base, int64_t exp);
int64_t nth_root128_i128_i64(__int128 n, int64_t k);
int64_t lower_bound_ptr_i32_i64_i64(int32_t* arr, int64_t n, int64_t key);
int64_t upper_bound_ptr_i32_i64_i64(int32_t* arr, int64_t n, int64_t key);
int32_t main(void);
int64_t isqrt64_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t isqrt128_i128(__int128 n) {
if (n <= 0) {
return 0;
}
if (n < 9223372036854775807) {
return isqrt64_i64(((int64_t)(n)));
}
__int128 x = n;
__int128 y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return ((int64_t)(x));
}
__int128 ipow128_i64_i64(int64_t base, int64_t exp) {
__int128 r = 1;
__int128 b = ((__int128)(base));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
r = (r * b);
}
b = (b * b);
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
int64_t nth_root128_i128_i64(__int128 n, int64_t k) {
if (n < 2) {
return ((int64_t)(n));
}
if (k == 1) {
if (n > 9223372036854775807) {
return 9223372036854775807;
}
return ((int64_t)(n));
}
int64_t lo = 1;
int64_t hi = 2;
while (ipow128_i64_i64(hi, k) <= n) {
if (hi > 1000000000) {
break;
}
hi = (hi * 2);
}
if (hi > 100000000) {
hi = 100000000;
}
while ((lo + 1) < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (ipow128_i64_i64(mid, k) <= n) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
int64_t lower_bound_ptr_i32_i64_i64(int32_t* arr, int64_t n, int64_t key) {
int64_t lo = 0;
int64_t hi = n;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (((int64_t)(arr[mid])) < key) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int64_t upper_bound_ptr_i32_i64_i64(int32_t* arr, int64_t n, int64_t key) {
int64_t lo = 0;
int64_t hi = n;
while (lo < hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
if (((int64_t)(arr[mid])) <= key) {
lo = (mid + 1);
} else {
hi = mid;
}
}
return lo;
}
int32_t main(void) {
__int128 Lmax = 500000000000;
__int128 N = FLOW_CHECKED_DIV(((Lmax * Lmax)), (3));
__int128 base_7_13 = (ipow128_i64_i64(7, 4) * ipow128_i64_i64(13, 4));
int64_t max_prime = isqrt128_i128(FLOW_CHECKED_DIV((N), (base_7_13)));
int8_t* sieve = (int8_t*)(calloc((max_prime + 1), 1));
int32_t* primes = (int32_t*)(calloc((FLOW_CHECKED_DIV((max_prime), (5)) + 10), 4));
int64_t pc = 0;
sieve[0] = 1;
sieve[1] = 1;
int64_t i = 2;
while (i <= max_prime) {
if (sieve[i] == 0) {
primes[pc] = ((int32_t)(i));
pc = (pc + 1);
int64_t j = (i * i);
while (j <= max_prime) {
sieve[j] = 1;
j = (j + i);
}
}
i = (i + 1);
}
int32_t* primes1 = (int32_t*)(calloc(pc, 4));
int64_t p1c = 0;
i = 0;
while (i < pc) {
int64_t p = ((int64_t)(primes[i]));
if (FLOW_CHECKED_MOD((p), (3)) == 1) {
primes1[p1c] = ((int32_t)(p));
p1c = (p1c + 1);
}
i = (i + 1);
}
__int128 A_min = (base_7_13 * ipow128_i64_i64(19, 2));
int64_t Bmax = isqrt128_i128(FLOW_CHECKED_DIV((N), (A_min)));
int8_t* good = (int8_t*)(calloc((Bmax + 1), 1));
i = 1;
while (i <= Bmax) {
good[i] = 1;
i = (i + 1);
}
i = 0;
while (i < pc) {
int64_t p = ((int64_t)(primes[i]));
if (p > Bmax) {
break;
}
if ((p == 3 || FLOW_CHECKED_MOD((p), (3)) == 1)) {
int64_t j = p;
while (j <= Bmax) {
good[j] = 0;
j = (j + p);
}
}
i = (i + 1);
}
int32_t* prefix_B = (int32_t*)(calloc((Bmax + 1), 4));
int64_t s = 0;
i = 1;
while (i <= Bmax) {
if (good[i] != 0) {
s = (s + 1);
}
prefix_B[i] = ((int32_t)(s));
i = (i + 1);
}
int64_t GCAP = FLOW_CHECKED_SHL((1), (22));
__int128* gkeys = (__int128*)(calloc(GCAP, 16));
int64_t* gvals = (int64_t*)(calloc(GCAP, 8));
int8_t* gused = (int8_t*)(calloc(GCAP, 1));
int64_t ans = 0;
__int128 p24 = ipow128_i64_i64(7, 24);
int64_t qmax = isqrt128_i128(FLOW_CHECKED_DIV((N), (p24)));
int64_t q_end = upper_bound_ptr_i32_i64_i64(primes1, p1c, qmax);
int64_t qi = 0;
while (qi < q_end) {
int64_t q = ((int64_t)(primes1[qi]));
if (q != 7) {
__int128 A = ((p24 * ((__int128)(q))) * ((__int128)(q)));
__int128 lim = FLOW_CHECKED_DIV((N), (A));
int64_t h = ((int64_t)(FLOW_CHECKED_MOD((lim), (((__int128)(GCAP))))));
if (h < 0) {
h = (0 - h);
}
int64_t slot = h;
while ((gused[slot] != 0 && gkeys[slot] != lim)) {
slot = ((slot + 1) & (GCAP - 1));
}
int64_t g = 0;
if (gused[slot] != 0) {
g = gvals[slot];
} else {
__int128 mm = lim;
while (mm > 0) {
int64_t r = isqrt128_i128(mm);
int64_t x = r;
if (x > Bmax) {
x = Bmax;
}
if (x > 0) {
g = (g + ((int64_t)(prefix_B[x])));
}
mm = FLOW_CHECKED_DIV((mm), (3));
}
gused[slot] = 1;
gkeys[slot] = lim;
gvals[slot] = g;
}
ans = (ans + g);
}
qi = (qi + 1);
}
int64_t pi = 0;
while (pi < p1c) {
int64_t p = ((int64_t)(primes1[pi]));
__int128 p14 = ipow128_i64_i64(p, 14);
if (p14 > N) {
break;
}
int64_t max_q = nth_root128_i128_i64(FLOW_CHECKED_DIV((N), (p14)), 4);
int64_t qe = upper_bound_ptr_i32_i64_i64(primes1, p1c, max_q);
qi = 0;
while (qi < qe) {
int64_t q = ((int64_t)(primes1[qi]));
if (q != p) {
__int128 q4 = ipow128_i64_i64(q, 4);
__int128 lim = FLOW_CHECKED_DIV((N), ((p14 * q4)));
int64_t h = ((int64_t)(FLOW_CHECKED_MOD((lim), (((__int128)(GCAP))))));
if (h < 0) {
h = (0 - h);
}
int64_t slot = h;
while ((gused[slot] != 0 && gkeys[slot] != lim)) {
slot = ((slot + 1) & (GCAP - 1));
}
int64_t g = 0;
if (gused[slot] != 0) {
g = gvals[slot];
} else {
__int128 mm = lim;
while (mm > 0) {
int64_t r = isqrt128_i128(mm);
int64_t x = r;
if (x > Bmax) {
x = Bmax;
}
if (x > 0) {
g = (g + ((int64_t)(prefix_B[x])));
}
mm = FLOW_CHECKED_DIV((mm), (3));
}
gused[slot] = 1;
gkeys[slot] = lim;
gvals[slot] = g;
}
ans = (ans + g);
}
qi = (qi + 1);
}
pi = (pi + 1);
}
int64_t p_max = nth_root128_i128_i64(FLOW_CHECKED_DIV((N), (49)), 8);
int64_t p_end = upper_bound_ptr_i32_i64_i64(primes1, p1c, p_max);
pi = 0;
while (pi < p_end) {
int64_t p = ((int64_t)(primes1[pi]));
__int128 p4 = ipow128_i64_i64(p, 4);
__int128 rem = FLOW_CHECKED_DIV((N), ((p4 * 49)));
if (rem == 0) {
break;
}
int64_t qmax2 = nth_root128_i128_i64(rem, 4);
int64_t q_start = upper_bound_ptr_i32_i64_i64(primes1, p1c, p);
int64_t qe2 = upper_bound_ptr_i32_i64_i64(primes1, p1c, qmax2);
qi = q_start;
while (qi < qe2) {
int64_t q = ((int64_t)(primes1[qi]));
__int128 base = (p4 * ipow128_i64_i64(q, 4));
__int128 C = FLOW_CHECKED_DIV((N), (base));
if (C > 0) {
int64_t Rmax = isqrt128_i128(C);
if (Rmax >= 7) {
int64_t r_low = 7;
while (r_low <= Rmax) {
__int128 tt = FLOW_CHECKED_DIV((C), ((((__int128)(r_low)) * ((__int128)(r_low)))));
if (tt == 0) {
break;
}
int64_t r_high = isqrt128_i128(FLOW_CHECKED_DIV((C), (tt)));
if (r_high > Rmax) {
r_high = Rmax;
}
int64_t cnt = (upper_bound_ptr_i32_i64_i64(primes1, p1c, r_high) - lower_bound_ptr_i32_i64_i64(primes1, p1c, r_low));
if ((r_low <= p && p <= r_high)) {
cnt = (cnt - 1);
}
if (((p != q && r_low <= q) && q <= r_high)) {
cnt = (cnt - 1);
}
if (cnt > 0) {
__int128 lim = tt;
int64_t h = ((int64_t)(FLOW_CHECKED_MOD((lim), (((__int128)(GCAP))))));
if (h < 0) {
h = (0 - h);
}
int64_t slot = h;
while ((gused[slot] != 0 && gkeys[slot] != lim)) {
slot = ((slot + 1) & (GCAP - 1));
}
int64_t g = 0;
if (gused[slot] != 0) {
g = gvals[slot];
} else {
__int128 mm = lim;
while (mm > 0) {
int64_t r = isqrt128_i128(mm);
int64_t x = r;
if (x > Bmax) {
x = Bmax;
}
if (x > 0) {
g = (g + ((int64_t)(prefix_B[x])));
}
mm = FLOW_CHECKED_DIV((mm), (3));
}
gused[slot] = 1;
gkeys[slot] = lim;
gvals[slot] = g;
}
ans = (ans + (cnt * g));
}
r_low = (r_high + 1);
}
}
}
qi = (qi + 1);
}
pi = (pi + 1);
}
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 @isqrt64(%arg0: i64) -> i64 {
%0 = arith.constant 0 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi sle, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %6 : i64, !llvm.ptr
%7 = llvm.load %6 : !llvm.ptr -> i64
%8 = arith.constant 1 : i32
%10 = arith.extsi %8 : i32 to i64
%9 = arith.addi %7, %10 : i64
%11 = arith.constant 2 : i32
%13 = arith.extsi %11 : i32 to i64
%12 = arith.divsi %9, %13 : i64
%14 = llvm.mlir.constant(1 : i64) : i64
%15 = llvm.alloca %14 x i64 : (i64) -> !llvm.ptr
llvm.store %12, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%16 = llvm.load %15 : !llvm.ptr -> i64
%17 = llvm.load %6 : !llvm.ptr -> i64
%18 = arith.cmpi slt, %16, %17 : i64
cf.cond_br %18, ^bb4, ^bb5
^bb4:
%19 = llvm.load %15 : !llvm.ptr -> i64
llvm.store %19, %6 : i64, !llvm.ptr
%20 = llvm.load %6 : !llvm.ptr -> i64
%21 = llvm.load %6 : !llvm.ptr -> i64
%22 = arith.divsi %arg0, %21 : i64
%23 = arith.addi %20, %22 : i64
%24 = arith.constant 2 : i32
%26 = arith.extsi %24 : i32 to i64
%25 = arith.divsi %23, %26 : i64
llvm.store %25, %15 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%27 = llvm.load %6 : !llvm.ptr -> i64
func.return %27 : i64
}
func.func @isqrt128(%arg0: i128) -> i64 {
%28 = arith.constant 0 : i32
%30 = arith.trunci %arg0 : i128 to i64
%31 = arith.extsi %28 : i32 to i64
%29 = arith.cmpi sle, %30, %31 : i64
cf.cond_br %29, ^bb6, ^bb7
^bb6:
%32 = arith.constant 0 : i32
%33 = arith.extsi %32 : i32 to i64
func.return %33 : i64
^bb7:
cf.br ^bb8
^bb8:
%34 = arith.constant 9223372032559808511 : i32
%36 = arith.trunci %arg0 : i128 to i64
%37 = arith.extsi %34 : i32 to i64
%35 = arith.cmpi slt, %36, %37 : i64
cf.cond_br %35, ^bb9, ^bb10
^bb9:
%39 = arith.trunci %arg0 : i128 to i64
%38 = func.call @isqrt64(%39) : (i64) -> i64
func.return %38 : i64
^bb10:
cf.br ^bb11
^bb11:
%40 = llvm.mlir.constant(1 : i64) : i64
%41 = llvm.alloca %40 x i128 : (i64) -> !llvm.ptr
llvm.store %arg0, %41 : i128, !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> i128
%43 = arith.constant 1 : i32
%45 = arith.trunci %42 : i128 to i64
%46 = arith.extsi %43 : i32 to i64
%44 = arith.addi %45, %46 : i64
%47 = arith.constant 2 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.divsi %44, %49 : i64
%50 = arith.extsi %48 : i64 to i128
%51 = llvm.mlir.constant(1 : i64) : i64
%52 = llvm.alloca %51 x i128 : (i64) -> !llvm.ptr
llvm.store %50, %52 : i128, !llvm.ptr
cf.br ^bb12
^bb12:
%53 = llvm.load %52 : !llvm.ptr -> i128
%54 = llvm.load %41 : !llvm.ptr -> i128
%56 = arith.trunci %53 : i128 to i64
%57 = arith.trunci %54 : i128 to i64
%55 = arith.cmpi slt, %56, %57 : i64
cf.cond_br %55, ^bb13, ^bb14
^bb13:
%58 = llvm.load %52 : !llvm.ptr -> i128
llvm.store %58, %41 : i128, !llvm.ptr
%59 = llvm.load %41 : !llvm.ptr -> i128
%60 = llvm.load %41 : !llvm.ptr -> i128
%62 = arith.trunci %arg0 : i128 to i64
%63 = arith.trunci %60 : i128 to i64
%61 = arith.divsi %62, %63 : i64
%65 = arith.trunci %59 : i128 to i64
%64 = arith.addi %65, %61 : i64
%66 = arith.constant 2 : i32
%68 = arith.extsi %66 : i32 to i64
%67 = arith.divsi %64, %68 : i64
%69 = arith.extsi %67 : i64 to i128
llvm.store %69, %52 : i128, !llvm.ptr
cf.br ^bb12
^bb14:
%70 = llvm.load %41 : !llvm.ptr -> i128
%71 = arith.trunci %70 : i128 to i64
func.return %71 : i64
}
func.func @ipow128(%arg0: i64, %arg1: i64) -> i128 {
%72 = arith.constant 1 : i32
%73 = arith.extsi %72 : i32 to i128
%74 = llvm.mlir.constant(1 : i64) : i64
%75 = llvm.alloca %74 x i128 : (i64) -> !llvm.ptr
llvm.store %73, %75 : i128, !llvm.ptr
%76 = arith.extsi %arg0 : i64 to i128
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i128 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i128, !llvm.ptr
%79 = llvm.mlir.constant(1 : i64) : i64
%80 = llvm.alloca %79 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %80 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%81 = llvm.load %80 : !llvm.ptr -> i64
%82 = arith.constant 0 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.cmpi sgt, %81, %84 : i64
cf.cond_br %83, ^bb16, ^bb17
^bb16:
%85 = llvm.load %80 : !llvm.ptr -> i64
%86 = arith.constant 2 : i32
%88 = arith.extsi %86 : i32 to i64
%87 = arith.remsi %85, %88 : i64
%89 = arith.constant 1 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.cmpi eq, %87, %91 : i64
cf.cond_br %90, ^bb18, ^bb19
^bb18:
%92 = llvm.load %75 : !llvm.ptr -> i128
%93 = llvm.load %78 : !llvm.ptr -> i128
%95 = arith.trunci %92 : i128 to i64
%96 = arith.trunci %93 : i128 to i64
%94 = arith.muli %95, %96 : i64
%97 = arith.extsi %94 : i64 to i128
llvm.store %97, %75 : i128, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%98 = llvm.load %78 : !llvm.ptr -> i128
%99 = llvm.load %78 : !llvm.ptr -> i128
%101 = arith.trunci %98 : i128 to i64
%102 = arith.trunci %99 : i128 to i64
%100 = arith.muli %101, %102 : i64
%103 = arith.extsi %100 : i64 to i128
llvm.store %103, %78 : i128, !llvm.ptr
%104 = llvm.load %80 : !llvm.ptr -> i64
%105 = arith.constant 2 : i32
%107 = arith.extsi %105 : i32 to i64
%106 = arith.divsi %104, %107 : i64
llvm.store %106, %80 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%108 = llvm.load %75 : !llvm.ptr -> i128
func.return %108 : i128
}
func.func @nth_root128(%arg0: i128, %arg1: i64) -> i64 {
%109 = arith.constant 2 : i32
%111 = arith.trunci %arg0 : i128 to i64
%112 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi slt, %111, %112 : i64
cf.cond_br %110, ^bb21, ^bb22
^bb21:
%113 = arith.trunci %arg0 : i128 to i64
func.return %113 : i64
^bb22:
cf.br ^bb23
^bb23:
%114 = arith.constant 1 : i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.cmpi eq, %arg1, %116 : i64
cf.cond_br %115, ^bb24, ^bb25
^bb24:
%117 = arith.constant 9223372032559808511 : i32
%119 = arith.trunci %arg0 : i128 to i64
%120 = arith.extsi %117 : i32 to i64
%118 = arith.cmpi sgt, %119, %120 : i64
cf.cond_br %118, ^bb27, ^bb28
^bb27:
%121 = arith.constant 9223372032559808511 : i32
%122 = arith.extsi %121 : i32 to i64
func.return %122 : i64
^bb28:
cf.br ^bb29
^bb29:
%123 = arith.trunci %arg0 : i128 to i64
func.return %123 : i64
^bb25:
cf.br ^bb26
^bb26:
%124 = arith.constant 1 : i32
%125 = arith.extsi %124 : i32 to i64
%126 = llvm.mlir.constant(1 : i64) : i64
%127 = llvm.alloca %126 x i64 : (i64) -> !llvm.ptr
llvm.store %125, %127 : i64, !llvm.ptr
%128 = arith.constant 2 : i32
%129 = arith.extsi %128 : i32 to i64
%130 = llvm.mlir.constant(1 : i64) : i64
%131 = llvm.alloca %130 x i64 : (i64) -> !llvm.ptr
llvm.store %129, %131 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%133 = llvm.load %131 : !llvm.ptr -> i64
%132 = func.call @ipow128(%133, %arg1) : (i64, i64) -> i128
%135 = arith.trunci %132 : i128 to i64
%136 = arith.trunci %arg0 : i128 to i64
%134 = arith.cmpi sle, %135, %136 : i64
cf.cond_br %134, ^bb31, ^bb32
^bb31:
%137 = llvm.load %131 : !llvm.ptr -> i64
%138 = arith.constant 1000000000 : i32
%140 = arith.extsi %138 : i32 to i64
%139 = arith.cmpi sgt, %137, %140 : i64
cf.cond_br %139, ^bb33, ^bb34
^bb33:
cf.br ^bb32
^bb34:
cf.br ^bb35
^bb35:
%141 = llvm.load %131 : !llvm.ptr -> i64
%142 = arith.constant 2 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.muli %141, %144 : i64
llvm.store %143, %131 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
%145 = llvm.load %131 : !llvm.ptr -> i64
%146 = arith.constant 100000000 : i32
%148 = arith.extsi %146 : i32 to i64
%147 = arith.cmpi sgt, %145, %148 : i64
cf.cond_br %147, ^bb36, ^bb37
^bb36:
%149 = arith.constant 100000000 : i32
%150 = arith.extsi %149 : i32 to i64
llvm.store %150, %131 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
cf.br ^bb39
^bb39:
%151 = llvm.load %127 : !llvm.ptr -> i64
%152 = arith.constant 1 : i32
%154 = arith.extsi %152 : i32 to i64
%153 = arith.addi %151, %154 : i64
%155 = llvm.load %131 : !llvm.ptr -> i64
%156 = arith.cmpi slt, %153, %155 : i64
cf.cond_br %156, ^bb40, ^bb41
^bb40:
%157 = llvm.load %127 : !llvm.ptr -> i64
%158 = llvm.load %131 : !llvm.ptr -> i64
%159 = arith.addi %157, %158 : i64
%160 = arith.constant 2 : i32
%162 = arith.extsi %160 : i32 to i64
%161 = arith.divsi %159, %162 : i64
%163 = func.call @ipow128(%161, %arg1) : (i64, i64) -> i128
%165 = arith.trunci %163 : i128 to i64
%166 = arith.trunci %arg0 : i128 to i64
%164 = arith.cmpi sle, %165, %166 : i64
cf.cond_br %164, ^bb42, ^bb43
^bb42:
llvm.store %161, %127 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
llvm.store %161, %131 : i64, !llvm.ptr
cf.br ^bb44
^bb44:
cf.br ^bb39
^bb41:
%167 = llvm.load %127 : !llvm.ptr -> i64
func.return %167 : i64
}
func.func @lower_bound(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%168 = arith.constant 0 : i32
%169 = arith.extsi %168 : i32 to i64
%170 = llvm.mlir.constant(1 : i64) : i64
%171 = llvm.alloca %170 x i64 : (i64) -> !llvm.ptr
llvm.store %169, %171 : i64, !llvm.ptr
%172 = llvm.mlir.constant(1 : i64) : i64
%173 = llvm.alloca %172 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %173 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%174 = llvm.load %171 : !llvm.ptr -> i64
%175 = llvm.load %173 : !llvm.ptr -> i64
%176 = arith.cmpi slt, %174, %175 : i64
cf.cond_br %176, ^bb46, ^bb47
^bb46:
%177 = llvm.load %171 : !llvm.ptr -> i64
%178 = llvm.load %173 : !llvm.ptr -> i64
%179 = arith.addi %177, %178 : i64
%180 = arith.constant 2 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.divsi %179, %182 : i64
%184 = llvm.getelementptr %arg0[%181] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%183 = llvm.load %184 : !llvm.ptr -> i32
%185 = arith.extsi %183 : i32 to i64
%186 = arith.cmpi slt, %185, %arg2 : i64
cf.cond_br %186, ^bb48, ^bb49
^bb48:
%187 = arith.constant 1 : i32
%189 = arith.extsi %187 : i32 to i64
%188 = arith.addi %181, %189 : i64
llvm.store %188, %171 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
llvm.store %181, %173 : i64, !llvm.ptr
cf.br ^bb50
^bb50:
cf.br ^bb45
^bb47:
%190 = llvm.load %171 : !llvm.ptr -> i64
func.return %190 : i64
}
func.func @upper_bound(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> i64 {
%191 = arith.constant 0 : i32
%192 = arith.extsi %191 : i32 to i64
%193 = llvm.mlir.constant(1 : i64) : i64
%194 = llvm.alloca %193 x i64 : (i64) -> !llvm.ptr
llvm.store %192, %194 : i64, !llvm.ptr
%195 = llvm.mlir.constant(1 : i64) : i64
%196 = llvm.alloca %195 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %196 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%197 = llvm.load %194 : !llvm.ptr -> i64
%198 = llvm.load %196 : !llvm.ptr -> i64
%199 = arith.cmpi slt, %197, %198 : i64
cf.cond_br %199, ^bb52, ^bb53
^bb52:
%200 = llvm.load %194 : !llvm.ptr -> i64
%201 = llvm.load %196 : !llvm.ptr -> i64
%202 = arith.addi %200, %201 : i64
%203 = arith.constant 2 : i32
%205 = arith.extsi %203 : i32 to i64
%204 = arith.divsi %202, %205 : i64
%207 = llvm.getelementptr %arg0[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%206 = llvm.load %207 : !llvm.ptr -> i32
%208 = arith.extsi %206 : i32 to i64
%209 = arith.cmpi sle, %208, %arg2 : i64
cf.cond_br %209, ^bb54, ^bb55
^bb54:
%210 = arith.constant 1 : i32
%212 = arith.extsi %210 : i32 to i64
%211 = arith.addi %204, %212 : i64
llvm.store %211, %194 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
llvm.store %204, %196 : i64, !llvm.ptr
cf.br ^bb56
^bb56:
cf.br ^bb51
^bb53:
%213 = llvm.load %194 : !llvm.ptr -> i64
func.return %213 : i64
}
func.func @main() -> i32 {
%214 = arith.constant 495705032704 : i32
%215 = arith.extsi %214 : i32 to i128
%217 = arith.trunci %215 : i128 to i64
%218 = arith.trunci %215 : i128 to i64
%216 = arith.muli %217, %218 : i64
%219 = arith.constant 3 : i32
%221 = arith.extsi %219 : i32 to i64
%220 = arith.divsi %216, %221 : i64
%222 = arith.extsi %220 : i64 to i128
%224 = arith.constant 7 : i32
%225 = arith.constant 4 : i32
%226 = arith.extsi %224 : i32 to i64
%227 = arith.extsi %225 : i32 to i64
%223 = func.call @ipow128(%226, %227) : (i64, i64) -> i128
%229 = arith.constant 13 : i32
%230 = arith.constant 4 : i32
%231 = arith.extsi %229 : i32 to i64
%232 = arith.extsi %230 : i32 to i64
%228 = func.call @ipow128(%231, %232) : (i64, i64) -> i128
%234 = arith.trunci %223 : i128 to i64
%235 = arith.trunci %228 : i128 to i64
%233 = arith.muli %234, %235 : i64
%236 = arith.extsi %233 : i64 to i128
%239 = arith.trunci %222 : i128 to i64
%240 = arith.trunci %236 : i128 to i64
%238 = arith.divsi %239, %240 : i64
%241 = arith.extsi %238 : i64 to i128
%237 = func.call @isqrt128(%241) : (i128) -> i64
%243 = arith.constant 1 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.addi %237, %245 : i64
%246 = arith.constant 1 : i32
%247 = arith.extsi %246 : i32 to i64
%242 = func.call @calloc(%244, %247) : (i64, i64) -> !llvm.ptr
%249 = arith.constant 5 : i32
%251 = arith.extsi %249 : i32 to i64
%250 = arith.divsi %237, %251 : i64
%252 = arith.constant 10 : i32
%254 = arith.extsi %252 : i32 to i64
%253 = arith.addi %250, %254 : i64
%255 = arith.constant 4 : i32
%256 = arith.extsi %255 : i32 to i64
%248 = func.call @calloc(%253, %256) : (i64, i64) -> !llvm.ptr
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
%259 = llvm.mlir.constant(1 : i64) : i64
%260 = llvm.alloca %259 x i64 : (i64) -> !llvm.ptr
llvm.store %258, %260 : i64, !llvm.ptr
%261 = arith.constant 1 : i32
%262 = arith.constant 0 : i32
%263 = arith.trunci %261 : i32 to i8
%264 = arith.extsi %262 : i32 to i64
%265 = llvm.getelementptr %242[%264] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %263, %265 : i8, !llvm.ptr
%266 = arith.constant 1 : i32
%267 = arith.constant 1 : i32
%268 = arith.trunci %266 : i32 to i8
%269 = arith.extsi %267 : i32 to i64
%270 = llvm.getelementptr %242[%269] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %268, %270 : i8, !llvm.ptr
%271 = arith.constant 2 : i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.mlir.constant(1 : i64) : i64
%274 = llvm.alloca %273 x i64 : (i64) -> !llvm.ptr
llvm.store %272, %274 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%275 = llvm.load %274 : !llvm.ptr -> i64
%276 = arith.cmpi sle, %275, %237 : i64
cf.cond_br %276, ^bb58, ^bb59
^bb58:
%278 = llvm.load %274 : !llvm.ptr -> i64
%279 = llvm.getelementptr %242[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%277 = llvm.load %279 : !llvm.ptr -> i8
%280 = arith.constant 0 : i32
%282 = arith.extsi %277 : i8 to i32
%281 = arith.cmpi eq, %282, %280 : i32
cf.cond_br %281, ^bb60, ^bb61
^bb60:
%283 = llvm.load %274 : !llvm.ptr -> i64
%284 = arith.trunci %283 : i64 to i32
%285 = llvm.load %260 : !llvm.ptr -> i64
%286 = llvm.getelementptr %248[%285] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %284, %286 : i32, !llvm.ptr
%287 = llvm.load %260 : !llvm.ptr -> i64
%288 = arith.constant 1 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.addi %287, %290 : i64
llvm.store %289, %260 : i64, !llvm.ptr
%291 = llvm.load %274 : !llvm.ptr -> i64
%292 = llvm.load %274 : !llvm.ptr -> i64
%293 = arith.muli %291, %292 : i64
%294 = llvm.mlir.constant(1 : i64) : i64
%295 = llvm.alloca %294 x i64 : (i64) -> !llvm.ptr
llvm.store %293, %295 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%296 = llvm.load %295 : !llvm.ptr -> i64
%297 = arith.cmpi sle, %296, %237 : i64
cf.cond_br %297, ^bb64, ^bb65
^bb64:
%298 = arith.constant 1 : i32
%299 = llvm.load %295 : !llvm.ptr -> i64
%300 = arith.trunci %298 : i32 to i8
%301 = llvm.getelementptr %242[%299] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %300, %301 : i8, !llvm.ptr
%302 = llvm.load %295 : !llvm.ptr -> i64
%303 = llvm.load %274 : !llvm.ptr -> i64
%304 = arith.addi %302, %303 : i64
llvm.store %304, %295 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%305 = llvm.load %274 : !llvm.ptr -> i64
%306 = arith.constant 1 : i32
%308 = arith.extsi %306 : i32 to i64
%307 = arith.addi %305, %308 : i64
llvm.store %307, %274 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%310 = llvm.load %260 : !llvm.ptr -> i64
%311 = arith.constant 4 : i32
%312 = arith.extsi %311 : i32 to i64
%309 = func.call @calloc(%310, %312) : (i64, i64) -> !llvm.ptr
%313 = arith.constant 0 : i32
%314 = arith.extsi %313 : i32 to i64
%315 = llvm.mlir.constant(1 : i64) : i64
%316 = llvm.alloca %315 x i64 : (i64) -> !llvm.ptr
llvm.store %314, %316 : i64, !llvm.ptr
%317 = arith.constant 0 : i32
%318 = arith.extsi %317 : i32 to i64
llvm.store %318, %274 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%319 = llvm.load %274 : !llvm.ptr -> i64
%320 = llvm.load %260 : !llvm.ptr -> i64
%321 = arith.cmpi slt, %319, %320 : i64
cf.cond_br %321, ^bb67, ^bb68
^bb67:
%323 = llvm.load %274 : !llvm.ptr -> i64
%324 = llvm.getelementptr %248[%323] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%322 = llvm.load %324 : !llvm.ptr -> i32
%325 = arith.extsi %322 : i32 to i64
%326 = arith.constant 3 : i32
%328 = arith.extsi %326 : i32 to i64
%327 = arith.remsi %325, %328 : i64
%329 = arith.constant 1 : i32
%331 = arith.extsi %329 : i32 to i64
%330 = arith.cmpi eq, %327, %331 : i64
cf.cond_br %330, ^bb69, ^bb70
^bb69:
%332 = arith.trunci %325 : i64 to i32
%333 = llvm.load %316 : !llvm.ptr -> i64
%334 = llvm.getelementptr %309[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %332, %334 : i32, !llvm.ptr
%335 = llvm.load %316 : !llvm.ptr -> i64
%336 = arith.constant 1 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.addi %335, %338 : i64
llvm.store %337, %316 : i64, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%339 = llvm.load %274 : !llvm.ptr -> i64
%340 = arith.constant 1 : i32
%342 = arith.extsi %340 : i32 to i64
%341 = arith.addi %339, %342 : i64
llvm.store %341, %274 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%344 = arith.constant 19 : i32
%345 = arith.constant 2 : i32
%346 = arith.extsi %344 : i32 to i64
%347 = arith.extsi %345 : i32 to i64
%343 = func.call @ipow128(%346, %347) : (i64, i64) -> i128
%349 = arith.trunci %236 : i128 to i64
%350 = arith.trunci %343 : i128 to i64
%348 = arith.muli %349, %350 : i64
%351 = arith.extsi %348 : i64 to i128
%354 = arith.trunci %222 : i128 to i64
%355 = arith.trunci %351 : i128 to i64
%353 = arith.divsi %354, %355 : i64
%356 = arith.extsi %353 : i64 to i128
%352 = func.call @isqrt128(%356) : (i128) -> i64
%358 = arith.constant 1 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.addi %352, %360 : i64
%361 = arith.constant 1 : i32
%362 = arith.extsi %361 : i32 to i64
%357 = func.call @calloc(%359, %362) : (i64, i64) -> !llvm.ptr
%363 = arith.constant 1 : i32
%364 = arith.extsi %363 : i32 to i64
llvm.store %364, %274 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%365 = llvm.load %274 : !llvm.ptr -> i64
%366 = arith.cmpi sle, %365, %352 : i64
cf.cond_br %366, ^bb73, ^bb74
^bb73:
%367 = arith.constant 1 : i32
%368 = llvm.load %274 : !llvm.ptr -> i64
%369 = arith.trunci %367 : i32 to i8
%370 = llvm.getelementptr %357[%368] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %369, %370 : i8, !llvm.ptr
%371 = llvm.load %274 : !llvm.ptr -> i64
%372 = arith.constant 1 : i32
%374 = arith.extsi %372 : i32 to i64
%373 = arith.addi %371, %374 : i64
llvm.store %373, %274 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%375 = arith.constant 0 : i32
%376 = arith.extsi %375 : i32 to i64
llvm.store %376, %274 : i64, !llvm.ptr
cf.br ^bb75
^bb75:
%377 = llvm.load %274 : !llvm.ptr -> i64
%378 = llvm.load %260 : !llvm.ptr -> i64
%379 = arith.cmpi slt, %377, %378 : i64
cf.cond_br %379, ^bb76, ^bb77
^bb76:
%381 = llvm.load %274 : !llvm.ptr -> i64
%382 = llvm.getelementptr %248[%381] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%380 = llvm.load %382 : !llvm.ptr -> i32
%383 = arith.extsi %380 : i32 to i64
%384 = arith.cmpi sgt, %383, %352 : i64
cf.cond_br %384, ^bb78, ^bb79
^bb78:
cf.br ^bb77
^bb79:
cf.br ^bb80
^bb80:
%385 = arith.constant 3 : i32
%387 = arith.extsi %385 : i32 to i64
%386 = arith.cmpi eq, %383, %387 : i64
%388 = scf.if %386 -> (i1) {
%389 = arith.constant true
scf.yield %389 : i1
} else {
%390 = arith.constant 3 : i32
%392 = arith.extsi %390 : i32 to i64
%391 = arith.remsi %383, %392 : i64
%393 = arith.constant 1 : i32
%395 = arith.extsi %393 : i32 to i64
%394 = arith.cmpi eq, %391, %395 : i64
scf.yield %394 : i1
}
cf.cond_br %388, ^bb81, ^bb82
^bb81:
%396 = llvm.mlir.constant(1 : i64) : i64
%397 = llvm.alloca %396 x i64 : (i64) -> !llvm.ptr
llvm.store %383, %397 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%398 = llvm.load %397 : !llvm.ptr -> i64
%399 = arith.cmpi sle, %398, %352 : i64
cf.cond_br %399, ^bb85, ^bb86
^bb85:
%400 = arith.constant 0 : i32
%401 = llvm.load %397 : !llvm.ptr -> i64
%402 = arith.trunci %400 : i32 to i8
%403 = llvm.getelementptr %357[%401] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %402, %403 : i8, !llvm.ptr
%404 = llvm.load %397 : !llvm.ptr -> i64
%405 = arith.addi %404, %383 : i64
llvm.store %405, %397 : i64, !llvm.ptr
cf.br ^bb84
^bb86:
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%406 = llvm.load %274 : !llvm.ptr -> i64
%407 = arith.constant 1 : i32
%409 = arith.extsi %407 : i32 to i64
%408 = arith.addi %406, %409 : i64
llvm.store %408, %274 : i64, !llvm.ptr
cf.br ^bb75
^bb77:
%411 = arith.constant 1 : i32
%413 = arith.extsi %411 : i32 to i64
%412 = arith.addi %352, %413 : i64
%414 = arith.constant 4 : i32
%415 = arith.extsi %414 : i32 to i64
%410 = func.call @calloc(%412, %415) : (i64, i64) -> !llvm.ptr
%416 = arith.constant 0 : i32
%417 = arith.extsi %416 : i32 to i64
%418 = llvm.mlir.constant(1 : i64) : i64
%419 = llvm.alloca %418 x i64 : (i64) -> !llvm.ptr
llvm.store %417, %419 : i64, !llvm.ptr
%420 = arith.constant 1 : i32
%421 = arith.extsi %420 : i32 to i64
llvm.store %421, %274 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%422 = llvm.load %274 : !llvm.ptr -> i64
%423 = arith.cmpi sle, %422, %352 : i64
cf.cond_br %423, ^bb88, ^bb89
^bb88:
%425 = llvm.load %274 : !llvm.ptr -> i64
%426 = llvm.getelementptr %357[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%424 = llvm.load %426 : !llvm.ptr -> i8
%427 = arith.constant 0 : i32
%429 = arith.extsi %424 : i8 to i32
%428 = arith.cmpi ne, %429, %427 : i32
cf.cond_br %428, ^bb90, ^bb91
^bb90:
%430 = llvm.load %419 : !llvm.ptr -> i64
%431 = arith.constant 1 : i32
%433 = arith.extsi %431 : i32 to i64
%432 = arith.addi %430, %433 : i64
llvm.store %432, %419 : i64, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%434 = llvm.load %419 : !llvm.ptr -> i64
%435 = arith.trunci %434 : i64 to i32
%436 = llvm.load %274 : !llvm.ptr -> i64
%437 = llvm.getelementptr %410[%436] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %435, %437 : i32, !llvm.ptr
%438 = llvm.load %274 : !llvm.ptr -> i64
%439 = arith.constant 1 : i32
%441 = arith.extsi %439 : i32 to i64
%440 = arith.addi %438, %441 : i64
llvm.store %440, %274 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%442 = arith.constant 1 : i32
%443 = arith.constant 22 : i32
%444 = arith.shli %442, %443 : i32
%445 = arith.extsi %444 : i32 to i64
%447 = arith.constant 16 : i32
%448 = arith.extsi %447 : i32 to i64
%446 = func.call @calloc(%445, %448) : (i64, i64) -> !llvm.ptr
%450 = arith.constant 8 : i32
%451 = arith.extsi %450 : i32 to i64
%449 = func.call @calloc(%445, %451) : (i64, i64) -> !llvm.ptr
%453 = arith.constant 1 : i32
%454 = arith.extsi %453 : i32 to i64
%452 = func.call @calloc(%445, %454) : (i64, i64) -> !llvm.ptr
%455 = arith.constant 0 : i32
%456 = arith.extsi %455 : i32 to i64
%457 = llvm.mlir.constant(1 : i64) : i64
%458 = llvm.alloca %457 x i64 : (i64) -> !llvm.ptr
llvm.store %456, %458 : i64, !llvm.ptr
%460 = arith.constant 7 : i32
%461 = arith.constant 24 : i32
%462 = arith.extsi %460 : i32 to i64
%463 = arith.extsi %461 : i32 to i64
%459 = func.call @ipow128(%462, %463) : (i64, i64) -> i128
%466 = arith.trunci %222 : i128 to i64
%467 = arith.trunci %459 : i128 to i64
%465 = arith.divsi %466, %467 : i64
%468 = arith.extsi %465 : i64 to i128
%464 = func.call @isqrt128(%468) : (i128) -> i64
%470 = llvm.load %316 : !llvm.ptr -> i64
%469 = func.call @upper_bound(%309, %470, %464) : (!llvm.ptr, i64, i64) -> i64
%471 = arith.constant 0 : i32
%472 = arith.extsi %471 : i32 to i64
%473 = llvm.mlir.constant(1 : i64) : i64
%474 = llvm.alloca %473 x i64 : (i64) -> !llvm.ptr
llvm.store %472, %474 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%475 = llvm.load %474 : !llvm.ptr -> i64
%476 = arith.cmpi slt, %475, %469 : i64
cf.cond_br %476, ^bb94, ^bb95
^bb94:
%478 = llvm.load %474 : !llvm.ptr -> i64
%479 = llvm.getelementptr %309[%478] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%477 = llvm.load %479 : !llvm.ptr -> i32
%480 = arith.extsi %477 : i32 to i64
%481 = arith.constant 7 : i32
%483 = arith.extsi %481 : i32 to i64
%482 = arith.cmpi ne, %480, %483 : i64
cf.cond_br %482, ^bb96, ^bb97
^bb96:
%484 = arith.extsi %480 : i64 to i128
%486 = arith.trunci %459 : i128 to i64
%487 = arith.trunci %484 : i128 to i64
%485 = arith.muli %486, %487 : i64
%488 = arith.extsi %480 : i64 to i128
%490 = arith.trunci %488 : i128 to i64
%489 = arith.muli %485, %490 : i64
%491 = arith.extsi %489 : i64 to i128
%493 = arith.trunci %222 : i128 to i64
%494 = arith.trunci %491 : i128 to i64
%492 = arith.divsi %493, %494 : i64
%495 = arith.extsi %492 : i64 to i128
%496 = arith.extsi %445 : i64 to i128
%498 = arith.trunci %495 : i128 to i64
%499 = arith.trunci %496 : i128 to i64
%497 = arith.remsi %498, %499 : i64
%500 = llvm.mlir.constant(1 : i64) : i64
%501 = llvm.alloca %500 x i64 : (i64) -> !llvm.ptr
llvm.store %497, %501 : i64, !llvm.ptr
%502 = llvm.load %501 : !llvm.ptr -> i64
%503 = arith.constant 0 : i32
%505 = arith.extsi %503 : i32 to i64
%504 = arith.cmpi slt, %502, %505 : i64
cf.cond_br %504, ^bb99, ^bb100
^bb99:
%506 = arith.constant 0 : i32
%507 = llvm.load %501 : !llvm.ptr -> i64
%509 = arith.extsi %506 : i32 to i64
%508 = arith.subi %509, %507 : i64
llvm.store %508, %501 : i64, !llvm.ptr
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%510 = llvm.load %501 : !llvm.ptr -> i64
%511 = llvm.mlir.constant(1 : i64) : i64
%512 = llvm.alloca %511 x i64 : (i64) -> !llvm.ptr
llvm.store %510, %512 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%514 = llvm.load %512 : !llvm.ptr -> i64
%515 = llvm.getelementptr %452[%514] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%513 = llvm.load %515 : !llvm.ptr -> i8
%516 = arith.constant 0 : i32
%518 = arith.extsi %513 : i8 to i32
%517 = arith.cmpi ne, %518, %516 : i32
%519 = scf.if %517 -> (i1) {
%521 = llvm.load %512 : !llvm.ptr -> i64
%522 = llvm.getelementptr %446[%521] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%520 = llvm.load %522 : !llvm.ptr -> i128
%524 = arith.trunci %520 : i128 to i64
%525 = arith.trunci %495 : i128 to i64
%523 = arith.cmpi ne, %524, %525 : i64
scf.yield %523 : i1
} else {
%526 = arith.constant false
scf.yield %526 : i1
}
cf.cond_br %519, ^bb103, ^bb104
^bb103:
%527 = llvm.load %512 : !llvm.ptr -> i64
%528 = arith.constant 1 : i32
%530 = arith.extsi %528 : i32 to i64
%529 = arith.addi %527, %530 : i64
%531 = arith.constant 1 : i32
%533 = arith.extsi %531 : i32 to i64
%532 = arith.subi %445, %533 : i64
%534 = arith.andi %529, %532 : i64
llvm.store %534, %512 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
%535 = arith.constant 0 : i32
%536 = arith.extsi %535 : i32 to i64
%537 = llvm.mlir.constant(1 : i64) : i64
%538 = llvm.alloca %537 x i64 : (i64) -> !llvm.ptr
llvm.store %536, %538 : i64, !llvm.ptr
%540 = llvm.load %512 : !llvm.ptr -> i64
%541 = llvm.getelementptr %452[%540] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%539 = llvm.load %541 : !llvm.ptr -> i8
%542 = arith.constant 0 : i32
%544 = arith.extsi %539 : i8 to i32
%543 = arith.cmpi ne, %544, %542 : i32
cf.cond_br %543, ^bb105, ^bb106
^bb105:
%546 = llvm.load %512 : !llvm.ptr -> i64
%547 = llvm.getelementptr %449[%546] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%545 = llvm.load %547 : !llvm.ptr -> i64
llvm.store %545, %538 : i64, !llvm.ptr
cf.br ^bb107
^bb106:
%548 = llvm.mlir.constant(1 : i64) : i64
%549 = llvm.alloca %548 x i128 : (i64) -> !llvm.ptr
llvm.store %495, %549 : i128, !llvm.ptr
cf.br ^bb108
^bb108:
%550 = llvm.load %549 : !llvm.ptr -> i128
%551 = arith.constant 0 : i32
%553 = arith.trunci %550 : i128 to i64
%554 = arith.extsi %551 : i32 to i64
%552 = arith.cmpi sgt, %553, %554 : i64
cf.cond_br %552, ^bb109, ^bb110
^bb109:
%556 = llvm.load %549 : !llvm.ptr -> i128
%555 = func.call @isqrt128(%556) : (i128) -> i64
%557 = llvm.mlir.constant(1 : i64) : i64
%558 = llvm.alloca %557 x i64 : (i64) -> !llvm.ptr
llvm.store %555, %558 : i64, !llvm.ptr
%559 = llvm.load %558 : !llvm.ptr -> i64
%560 = arith.cmpi sgt, %559, %352 : i64
cf.cond_br %560, ^bb111, ^bb112
^bb111:
llvm.store %352, %558 : i64, !llvm.ptr
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%561 = llvm.load %558 : !llvm.ptr -> i64
%562 = arith.constant 0 : i32
%564 = arith.extsi %562 : i32 to i64
%563 = arith.cmpi sgt, %561, %564 : i64
cf.cond_br %563, ^bb114, ^bb115
^bb114:
%565 = llvm.load %538 : !llvm.ptr -> i64
%567 = llvm.load %558 : !llvm.ptr -> i64
%568 = llvm.getelementptr %410[%567] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%566 = llvm.load %568 : !llvm.ptr -> i32
%569 = arith.extsi %566 : i32 to i64
%570 = arith.addi %565, %569 : i64
llvm.store %570, %538 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%571 = llvm.load %549 : !llvm.ptr -> i128
%572 = arith.constant 3 : i32
%574 = arith.trunci %571 : i128 to i64
%575 = arith.extsi %572 : i32 to i64
%573 = arith.divsi %574, %575 : i64
%576 = arith.extsi %573 : i64 to i128
llvm.store %576, %549 : i128, !llvm.ptr
cf.br ^bb108
^bb110:
%577 = arith.constant 1 : i32
%578 = llvm.load %512 : !llvm.ptr -> i64
%579 = arith.trunci %577 : i32 to i8
%580 = llvm.getelementptr %452[%578] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %579, %580 : i8, !llvm.ptr
%581 = llvm.load %512 : !llvm.ptr -> i64
%582 = llvm.getelementptr %446[%581] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %495, %582 : i128, !llvm.ptr
%583 = llvm.load %538 : !llvm.ptr -> i64
%584 = llvm.load %512 : !llvm.ptr -> i64
%585 = llvm.getelementptr %449[%584] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %583, %585 : i64, !llvm.ptr
cf.br ^bb107
^bb107:
%586 = llvm.load %458 : !llvm.ptr -> i64
%587 = llvm.load %538 : !llvm.ptr -> i64
%588 = arith.addi %586, %587 : i64
llvm.store %588, %458 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%589 = llvm.load %474 : !llvm.ptr -> i64
%590 = arith.constant 1 : i32
%592 = arith.extsi %590 : i32 to i64
%591 = arith.addi %589, %592 : i64
llvm.store %591, %474 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
%593 = arith.constant 0 : i32
%594 = arith.extsi %593 : i32 to i64
%595 = llvm.mlir.constant(1 : i64) : i64
%596 = llvm.alloca %595 x i64 : (i64) -> !llvm.ptr
llvm.store %594, %596 : i64, !llvm.ptr
cf.br ^bb117
^bb117:
%597 = llvm.load %596 : !llvm.ptr -> i64
%598 = llvm.load %316 : !llvm.ptr -> i64
%599 = arith.cmpi slt, %597, %598 : i64
cf.cond_br %599, ^bb118, ^bb119
^bb118:
%601 = llvm.load %596 : !llvm.ptr -> i64
%602 = llvm.getelementptr %309[%601] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%600 = llvm.load %602 : !llvm.ptr -> i32
%603 = arith.extsi %600 : i32 to i64
%605 = arith.constant 14 : i32
%606 = arith.extsi %605 : i32 to i64
%604 = func.call @ipow128(%603, %606) : (i64, i64) -> i128
%608 = arith.trunci %604 : i128 to i64
%609 = arith.trunci %222 : i128 to i64
%607 = arith.cmpi sgt, %608, %609 : i64
cf.cond_br %607, ^bb120, ^bb121
^bb120:
cf.br ^bb119
^bb121:
cf.br ^bb122
^bb122:
%612 = arith.trunci %222 : i128 to i64
%613 = arith.trunci %604 : i128 to i64
%611 = arith.divsi %612, %613 : i64
%614 = arith.constant 4 : i32
%615 = arith.extsi %611 : i64 to i128
%616 = arith.extsi %614 : i32 to i64
%610 = func.call @nth_root128(%615, %616) : (i128, i64) -> i64
%618 = llvm.load %316 : !llvm.ptr -> i64
%617 = func.call @upper_bound(%309, %618, %610) : (!llvm.ptr, i64, i64) -> i64
%619 = arith.constant 0 : i32
%620 = arith.extsi %619 : i32 to i64
llvm.store %620, %474 : i64, !llvm.ptr
cf.br ^bb123
^bb123:
%621 = llvm.load %474 : !llvm.ptr -> i64
%622 = arith.cmpi slt, %621, %617 : i64
cf.cond_br %622, ^bb124, ^bb125
^bb124:
%624 = llvm.load %474 : !llvm.ptr -> i64
%625 = llvm.getelementptr %309[%624] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%623 = llvm.load %625 : !llvm.ptr -> i32
%626 = arith.extsi %623 : i32 to i64
%627 = arith.cmpi ne, %626, %603 : i64
cf.cond_br %627, ^bb126, ^bb127
^bb126:
%629 = arith.constant 4 : i32
%630 = arith.extsi %629 : i32 to i64
%628 = func.call @ipow128(%626, %630) : (i64, i64) -> i128
%632 = arith.trunci %604 : i128 to i64
%633 = arith.trunci %628 : i128 to i64
%631 = arith.muli %632, %633 : i64
%635 = arith.trunci %222 : i128 to i64
%634 = arith.divsi %635, %631 : i64
%636 = arith.extsi %634 : i64 to i128
%637 = arith.extsi %445 : i64 to i128
%639 = arith.trunci %636 : i128 to i64
%640 = arith.trunci %637 : i128 to i64
%638 = arith.remsi %639, %640 : i64
%641 = llvm.mlir.constant(1 : i64) : i64
%642 = llvm.alloca %641 x i64 : (i64) -> !llvm.ptr
llvm.store %638, %642 : i64, !llvm.ptr
%643 = llvm.load %642 : !llvm.ptr -> i64
%644 = arith.constant 0 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.cmpi slt, %643, %646 : i64
cf.cond_br %645, ^bb129, ^bb130
^bb129:
%647 = arith.constant 0 : i32
%648 = llvm.load %642 : !llvm.ptr -> i64
%650 = arith.extsi %647 : i32 to i64
%649 = arith.subi %650, %648 : i64
llvm.store %649, %642 : i64, !llvm.ptr
cf.br ^bb131
^bb130:
cf.br ^bb131
^bb131:
%651 = llvm.load %642 : !llvm.ptr -> i64
%652 = llvm.mlir.constant(1 : i64) : i64
%653 = llvm.alloca %652 x i64 : (i64) -> !llvm.ptr
llvm.store %651, %653 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%655 = llvm.load %653 : !llvm.ptr -> i64
%656 = llvm.getelementptr %452[%655] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%654 = llvm.load %656 : !llvm.ptr -> i8
%657 = arith.constant 0 : i32
%659 = arith.extsi %654 : i8 to i32
%658 = arith.cmpi ne, %659, %657 : i32
%660 = scf.if %658 -> (i1) {
%662 = llvm.load %653 : !llvm.ptr -> i64
%663 = llvm.getelementptr %446[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%661 = llvm.load %663 : !llvm.ptr -> i128
%665 = arith.trunci %661 : i128 to i64
%666 = arith.trunci %636 : i128 to i64
%664 = arith.cmpi ne, %665, %666 : i64
scf.yield %664 : i1
} else {
%667 = arith.constant false
scf.yield %667 : i1
}
cf.cond_br %660, ^bb133, ^bb134
^bb133:
%668 = llvm.load %653 : !llvm.ptr -> i64
%669 = arith.constant 1 : i32
%671 = arith.extsi %669 : i32 to i64
%670 = arith.addi %668, %671 : i64
%672 = arith.constant 1 : i32
%674 = arith.extsi %672 : i32 to i64
%673 = arith.subi %445, %674 : i64
%675 = arith.andi %670, %673 : i64
llvm.store %675, %653 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%676 = arith.constant 0 : i32
%677 = arith.extsi %676 : i32 to i64
%678 = llvm.mlir.constant(1 : i64) : i64
%679 = llvm.alloca %678 x i64 : (i64) -> !llvm.ptr
llvm.store %677, %679 : i64, !llvm.ptr
%681 = llvm.load %653 : !llvm.ptr -> i64
%682 = llvm.getelementptr %452[%681] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%680 = llvm.load %682 : !llvm.ptr -> i8
%683 = arith.constant 0 : i32
%685 = arith.extsi %680 : i8 to i32
%684 = arith.cmpi ne, %685, %683 : i32
cf.cond_br %684, ^bb135, ^bb136
^bb135:
%687 = llvm.load %653 : !llvm.ptr -> i64
%688 = llvm.getelementptr %449[%687] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%686 = llvm.load %688 : !llvm.ptr -> i64
llvm.store %686, %679 : i64, !llvm.ptr
cf.br ^bb137
^bb136:
%689 = llvm.mlir.constant(1 : i64) : i64
%690 = llvm.alloca %689 x i128 : (i64) -> !llvm.ptr
llvm.store %636, %690 : i128, !llvm.ptr
cf.br ^bb138
^bb138:
%691 = llvm.load %690 : !llvm.ptr -> i128
%692 = arith.constant 0 : i32
%694 = arith.trunci %691 : i128 to i64
%695 = arith.extsi %692 : i32 to i64
%693 = arith.cmpi sgt, %694, %695 : i64
cf.cond_br %693, ^bb139, ^bb140
^bb139:
%697 = llvm.load %690 : !llvm.ptr -> i128
%696 = func.call @isqrt128(%697) : (i128) -> i64
%698 = llvm.mlir.constant(1 : i64) : i64
%699 = llvm.alloca %698 x i64 : (i64) -> !llvm.ptr
llvm.store %696, %699 : i64, !llvm.ptr
%700 = llvm.load %699 : !llvm.ptr -> i64
%701 = arith.cmpi sgt, %700, %352 : i64
cf.cond_br %701, ^bb141, ^bb142
^bb141:
llvm.store %352, %699 : i64, !llvm.ptr
cf.br ^bb143
^bb142:
cf.br ^bb143
^bb143:
%702 = llvm.load %699 : !llvm.ptr -> i64
%703 = arith.constant 0 : i32
%705 = arith.extsi %703 : i32 to i64
%704 = arith.cmpi sgt, %702, %705 : i64
cf.cond_br %704, ^bb144, ^bb145
^bb144:
%706 = llvm.load %679 : !llvm.ptr -> i64
%708 = llvm.load %699 : !llvm.ptr -> i64
%709 = llvm.getelementptr %410[%708] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%707 = llvm.load %709 : !llvm.ptr -> i32
%710 = arith.extsi %707 : i32 to i64
%711 = arith.addi %706, %710 : i64
llvm.store %711, %679 : i64, !llvm.ptr
cf.br ^bb146
^bb145:
cf.br ^bb146
^bb146:
%712 = llvm.load %690 : !llvm.ptr -> i128
%713 = arith.constant 3 : i32
%715 = arith.trunci %712 : i128 to i64
%716 = arith.extsi %713 : i32 to i64
%714 = arith.divsi %715, %716 : i64
%717 = arith.extsi %714 : i64 to i128
llvm.store %717, %690 : i128, !llvm.ptr
cf.br ^bb138
^bb140:
%718 = arith.constant 1 : i32
%719 = llvm.load %653 : !llvm.ptr -> i64
%720 = arith.trunci %718 : i32 to i8
%721 = llvm.getelementptr %452[%719] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %720, %721 : i8, !llvm.ptr
%722 = llvm.load %653 : !llvm.ptr -> i64
%723 = llvm.getelementptr %446[%722] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %636, %723 : i128, !llvm.ptr
%724 = llvm.load %679 : !llvm.ptr -> i64
%725 = llvm.load %653 : !llvm.ptr -> i64
%726 = llvm.getelementptr %449[%725] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %724, %726 : i64, !llvm.ptr
cf.br ^bb137
^bb137:
%727 = llvm.load %458 : !llvm.ptr -> i64
%728 = llvm.load %679 : !llvm.ptr -> i64
%729 = arith.addi %727, %728 : i64
llvm.store %729, %458 : i64, !llvm.ptr
cf.br ^bb128
^bb127:
cf.br ^bb128
^bb128:
%730 = llvm.load %474 : !llvm.ptr -> i64
%731 = arith.constant 1 : i32
%733 = arith.extsi %731 : i32 to i64
%732 = arith.addi %730, %733 : i64
llvm.store %732, %474 : i64, !llvm.ptr
cf.br ^bb123
^bb125:
%734 = llvm.load %596 : !llvm.ptr -> i64
%735 = arith.constant 1 : i32
%737 = arith.extsi %735 : i32 to i64
%736 = arith.addi %734, %737 : i64
llvm.store %736, %596 : i64, !llvm.ptr
cf.br ^bb117
^bb119:
%739 = arith.constant 49 : i32
%741 = arith.trunci %222 : i128 to i64
%742 = arith.extsi %739 : i32 to i64
%740 = arith.divsi %741, %742 : i64
%743 = arith.constant 8 : i32
%744 = arith.extsi %740 : i64 to i128
%745 = arith.extsi %743 : i32 to i64
%738 = func.call @nth_root128(%744, %745) : (i128, i64) -> i64
%747 = llvm.load %316 : !llvm.ptr -> i64
%746 = func.call @upper_bound(%309, %747, %738) : (!llvm.ptr, i64, i64) -> i64
%748 = arith.constant 0 : i32
%749 = arith.extsi %748 : i32 to i64
llvm.store %749, %596 : i64, !llvm.ptr
cf.br ^bb147
^bb147:
%750 = llvm.load %596 : !llvm.ptr -> i64
%751 = arith.cmpi slt, %750, %746 : i64
cf.cond_br %751, ^bb148, ^bb149
^bb148:
%753 = llvm.load %596 : !llvm.ptr -> i64
%754 = llvm.getelementptr %309[%753] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%752 = llvm.load %754 : !llvm.ptr -> i32
%755 = arith.extsi %752 : i32 to i64
%757 = arith.constant 4 : i32
%758 = arith.extsi %757 : i32 to i64
%756 = func.call @ipow128(%755, %758) : (i64, i64) -> i128
%759 = arith.constant 49 : i32
%761 = arith.trunci %756 : i128 to i64
%762 = arith.extsi %759 : i32 to i64
%760 = arith.muli %761, %762 : i64
%764 = arith.trunci %222 : i128 to i64
%763 = arith.divsi %764, %760 : i64
%765 = arith.extsi %763 : i64 to i128
%766 = arith.constant 0 : i32
%768 = arith.trunci %765 : i128 to i64
%769 = arith.extsi %766 : i32 to i64
%767 = arith.cmpi eq, %768, %769 : i64
cf.cond_br %767, ^bb150, ^bb151
^bb150:
cf.br ^bb149
^bb151:
cf.br ^bb152
^bb152:
%771 = arith.constant 4 : i32
%772 = arith.extsi %771 : i32 to i64
%770 = func.call @nth_root128(%765, %772) : (i128, i64) -> i64
%774 = llvm.load %316 : !llvm.ptr -> i64
%773 = func.call @upper_bound(%309, %774, %755) : (!llvm.ptr, i64, i64) -> i64
%776 = llvm.load %316 : !llvm.ptr -> i64
%775 = func.call @upper_bound(%309, %776, %770) : (!llvm.ptr, i64, i64) -> i64
llvm.store %773, %474 : i64, !llvm.ptr
cf.br ^bb153
^bb153:
%777 = llvm.load %474 : !llvm.ptr -> i64
%778 = arith.cmpi slt, %777, %775 : i64
cf.cond_br %778, ^bb154, ^bb155
^bb154:
%780 = llvm.load %474 : !llvm.ptr -> i64
%781 = llvm.getelementptr %309[%780] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%779 = llvm.load %781 : !llvm.ptr -> i32
%782 = arith.extsi %779 : i32 to i64
%784 = arith.constant 4 : i32
%785 = arith.extsi %784 : i32 to i64
%783 = func.call @ipow128(%782, %785) : (i64, i64) -> i128
%787 = arith.trunci %756 : i128 to i64
%788 = arith.trunci %783 : i128 to i64
%786 = arith.muli %787, %788 : i64
%789 = arith.extsi %786 : i64 to i128
%791 = arith.trunci %222 : i128 to i64
%792 = arith.trunci %789 : i128 to i64
%790 = arith.divsi %791, %792 : i64
%793 = arith.extsi %790 : i64 to i128
%794 = arith.constant 0 : i32
%796 = arith.trunci %793 : i128 to i64
%797 = arith.extsi %794 : i32 to i64
%795 = arith.cmpi sgt, %796, %797 : i64
cf.cond_br %795, ^bb156, ^bb157
^bb156:
%798 = func.call @isqrt128(%793) : (i128) -> i64
%799 = arith.constant 7 : i32
%801 = arith.extsi %799 : i32 to i64
%800 = arith.cmpi sge, %798, %801 : i64
cf.cond_br %800, ^bb159, ^bb160
^bb159:
%802 = arith.constant 7 : i32
%803 = arith.extsi %802 : i32 to i64
%804 = llvm.mlir.constant(1 : i64) : i64
%805 = llvm.alloca %804 x i64 : (i64) -> !llvm.ptr
llvm.store %803, %805 : i64, !llvm.ptr
cf.br ^bb162
^bb162:
%806 = llvm.load %805 : !llvm.ptr -> i64
%807 = arith.cmpi sle, %806, %798 : i64
cf.cond_br %807, ^bb163, ^bb164
^bb163:
%808 = llvm.load %805 : !llvm.ptr -> i64
%809 = arith.extsi %808 : i64 to i128
%810 = llvm.load %805 : !llvm.ptr -> i64
%811 = arith.extsi %810 : i64 to i128
%813 = arith.trunci %809 : i128 to i64
%814 = arith.trunci %811 : i128 to i64
%812 = arith.muli %813, %814 : i64
%816 = arith.trunci %793 : i128 to i64
%815 = arith.divsi %816, %812 : i64
%817 = arith.extsi %815 : i64 to i128
%818 = arith.constant 0 : i32
%820 = arith.trunci %817 : i128 to i64
%821 = arith.extsi %818 : i32 to i64
%819 = arith.cmpi eq, %820, %821 : i64
cf.cond_br %819, ^bb165, ^bb166
^bb165:
cf.br ^bb164
^bb166:
cf.br ^bb167
^bb167:
%824 = arith.trunci %793 : i128 to i64
%825 = arith.trunci %817 : i128 to i64
%823 = arith.divsi %824, %825 : i64
%826 = arith.extsi %823 : i64 to i128
%822 = func.call @isqrt128(%826) : (i128) -> i64
%827 = llvm.mlir.constant(1 : i64) : i64
%828 = llvm.alloca %827 x i64 : (i64) -> !llvm.ptr
llvm.store %822, %828 : i64, !llvm.ptr
%829 = llvm.load %828 : !llvm.ptr -> i64
%830 = arith.cmpi sgt, %829, %798 : i64
cf.cond_br %830, ^bb168, ^bb169
^bb168:
llvm.store %798, %828 : i64, !llvm.ptr
cf.br ^bb170
^bb169:
cf.br ^bb170
^bb170:
%832 = llvm.load %316 : !llvm.ptr -> i64
%833 = llvm.load %828 : !llvm.ptr -> i64
%831 = func.call @upper_bound(%309, %832, %833) : (!llvm.ptr, i64, i64) -> i64
%835 = llvm.load %316 : !llvm.ptr -> i64
%836 = llvm.load %805 : !llvm.ptr -> i64
%834 = func.call @lower_bound(%309, %835, %836) : (!llvm.ptr, i64, i64) -> i64
%837 = arith.subi %831, %834 : i64
%838 = llvm.mlir.constant(1 : i64) : i64
%839 = llvm.alloca %838 x i64 : (i64) -> !llvm.ptr
llvm.store %837, %839 : i64, !llvm.ptr
%840 = llvm.load %805 : !llvm.ptr -> i64
%841 = arith.cmpi sle, %840, %755 : i64
%842 = scf.if %841 -> (i1) {
%843 = llvm.load %828 : !llvm.ptr -> i64
%844 = arith.cmpi sle, %755, %843 : i64
scf.yield %844 : i1
} else {
%845 = arith.constant false
scf.yield %845 : i1
}
cf.cond_br %842, ^bb171, ^bb172
^bb171:
%846 = llvm.load %839 : !llvm.ptr -> i64
%847 = arith.constant 1 : i32
%849 = arith.extsi %847 : i32 to i64
%848 = arith.subi %846, %849 : i64
llvm.store %848, %839 : i64, !llvm.ptr
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
%850 = arith.cmpi ne, %755, %782 : i64
%851 = scf.if %850 -> (i1) {
%852 = llvm.load %805 : !llvm.ptr -> i64
%853 = arith.cmpi sle, %852, %782 : i64
scf.yield %853 : i1
} else {
%854 = arith.constant false
scf.yield %854 : i1
}
%855 = scf.if %851 -> (i1) {
%856 = llvm.load %828 : !llvm.ptr -> i64
%857 = arith.cmpi sle, %782, %856 : i64
scf.yield %857 : i1
} else {
%858 = arith.constant false
scf.yield %858 : i1
}
cf.cond_br %855, ^bb174, ^bb175
^bb174:
%859 = llvm.load %839 : !llvm.ptr -> i64
%860 = arith.constant 1 : i32
%862 = arith.extsi %860 : i32 to i64
%861 = arith.subi %859, %862 : i64
llvm.store %861, %839 : i64, !llvm.ptr
cf.br ^bb176
^bb175:
cf.br ^bb176
^bb176:
%863 = llvm.load %839 : !llvm.ptr -> i64
%864 = arith.constant 0 : i32
%866 = arith.extsi %864 : i32 to i64
%865 = arith.cmpi sgt, %863, %866 : i64
cf.cond_br %865, ^bb177, ^bb178
^bb177:
%867 = arith.extsi %445 : i64 to i128
%869 = arith.trunci %817 : i128 to i64
%870 = arith.trunci %867 : i128 to i64
%868 = arith.remsi %869, %870 : i64
%871 = llvm.mlir.constant(1 : i64) : i64
%872 = llvm.alloca %871 x i64 : (i64) -> !llvm.ptr
llvm.store %868, %872 : i64, !llvm.ptr
%873 = llvm.load %872 : !llvm.ptr -> i64
%874 = arith.constant 0 : i32
%876 = arith.extsi %874 : i32 to i64
%875 = arith.cmpi slt, %873, %876 : i64
cf.cond_br %875, ^bb180, ^bb181
^bb180:
%877 = arith.constant 0 : i32
%878 = llvm.load %872 : !llvm.ptr -> i64
%880 = arith.extsi %877 : i32 to i64
%879 = arith.subi %880, %878 : i64
llvm.store %879, %872 : i64, !llvm.ptr
cf.br ^bb182
^bb181:
cf.br ^bb182
^bb182:
%881 = llvm.load %872 : !llvm.ptr -> i64
%882 = llvm.mlir.constant(1 : i64) : i64
%883 = llvm.alloca %882 x i64 : (i64) -> !llvm.ptr
llvm.store %881, %883 : i64, !llvm.ptr
cf.br ^bb183
^bb183:
%885 = llvm.load %883 : !llvm.ptr -> i64
%886 = llvm.getelementptr %452[%885] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%884 = llvm.load %886 : !llvm.ptr -> i8
%887 = arith.constant 0 : i32
%889 = arith.extsi %884 : i8 to i32
%888 = arith.cmpi ne, %889, %887 : i32
%890 = scf.if %888 -> (i1) {
%892 = llvm.load %883 : !llvm.ptr -> i64
%893 = llvm.getelementptr %446[%892] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%891 = llvm.load %893 : !llvm.ptr -> i128
%895 = arith.trunci %891 : i128 to i64
%896 = arith.trunci %817 : i128 to i64
%894 = arith.cmpi ne, %895, %896 : i64
scf.yield %894 : i1
} else {
%897 = arith.constant false
scf.yield %897 : i1
}
cf.cond_br %890, ^bb184, ^bb185
^bb184:
%898 = llvm.load %883 : !llvm.ptr -> i64
%899 = arith.constant 1 : i32
%901 = arith.extsi %899 : i32 to i64
%900 = arith.addi %898, %901 : i64
%902 = arith.constant 1 : i32
%904 = arith.extsi %902 : i32 to i64
%903 = arith.subi %445, %904 : i64
%905 = arith.andi %900, %903 : i64
llvm.store %905, %883 : i64, !llvm.ptr
cf.br ^bb183
^bb185:
%906 = arith.constant 0 : i32
%907 = arith.extsi %906 : i32 to i64
%908 = llvm.mlir.constant(1 : i64) : i64
%909 = llvm.alloca %908 x i64 : (i64) -> !llvm.ptr
llvm.store %907, %909 : i64, !llvm.ptr
%911 = llvm.load %883 : !llvm.ptr -> i64
%912 = llvm.getelementptr %452[%911] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%910 = llvm.load %912 : !llvm.ptr -> i8
%913 = arith.constant 0 : i32
%915 = arith.extsi %910 : i8 to i32
%914 = arith.cmpi ne, %915, %913 : i32
cf.cond_br %914, ^bb186, ^bb187
^bb186:
%917 = llvm.load %883 : !llvm.ptr -> i64
%918 = llvm.getelementptr %449[%917] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%916 = llvm.load %918 : !llvm.ptr -> i64
llvm.store %916, %909 : i64, !llvm.ptr
cf.br ^bb188
^bb187:
%919 = llvm.mlir.constant(1 : i64) : i64
%920 = llvm.alloca %919 x i128 : (i64) -> !llvm.ptr
llvm.store %817, %920 : i128, !llvm.ptr
cf.br ^bb189
^bb189:
%921 = llvm.load %920 : !llvm.ptr -> i128
%922 = arith.constant 0 : i32
%924 = arith.trunci %921 : i128 to i64
%925 = arith.extsi %922 : i32 to i64
%923 = arith.cmpi sgt, %924, %925 : i64
cf.cond_br %923, ^bb190, ^bb191
^bb190:
%927 = llvm.load %920 : !llvm.ptr -> i128
%926 = func.call @isqrt128(%927) : (i128) -> i64
%928 = llvm.mlir.constant(1 : i64) : i64
%929 = llvm.alloca %928 x i64 : (i64) -> !llvm.ptr
llvm.store %926, %929 : i64, !llvm.ptr
%930 = llvm.load %929 : !llvm.ptr -> i64
%931 = arith.cmpi sgt, %930, %352 : i64
cf.cond_br %931, ^bb192, ^bb193
^bb192:
llvm.store %352, %929 : i64, !llvm.ptr
cf.br ^bb194
^bb193:
cf.br ^bb194
^bb194:
%932 = llvm.load %929 : !llvm.ptr -> i64
%933 = arith.constant 0 : i32
%935 = arith.extsi %933 : i32 to i64
%934 = arith.cmpi sgt, %932, %935 : i64
cf.cond_br %934, ^bb195, ^bb196
^bb195:
%936 = llvm.load %909 : !llvm.ptr -> i64
%938 = llvm.load %929 : !llvm.ptr -> i64
%939 = llvm.getelementptr %410[%938] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%937 = llvm.load %939 : !llvm.ptr -> i32
%940 = arith.extsi %937 : i32 to i64
%941 = arith.addi %936, %940 : i64
llvm.store %941, %909 : i64, !llvm.ptr
cf.br ^bb197
^bb196:
cf.br ^bb197
^bb197:
%942 = llvm.load %920 : !llvm.ptr -> i128
%943 = arith.constant 3 : i32
%945 = arith.trunci %942 : i128 to i64
%946 = arith.extsi %943 : i32 to i64
%944 = arith.divsi %945, %946 : i64
%947 = arith.extsi %944 : i64 to i128
llvm.store %947, %920 : i128, !llvm.ptr
cf.br ^bb189
^bb191:
%948 = arith.constant 1 : i32
%949 = llvm.load %883 : !llvm.ptr -> i64
%950 = arith.trunci %948 : i32 to i8
%951 = llvm.getelementptr %452[%949] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %950, %951 : i8, !llvm.ptr
%952 = llvm.load %883 : !llvm.ptr -> i64
%953 = llvm.getelementptr %446[%952] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %817, %953 : i128, !llvm.ptr
%954 = llvm.load %909 : !llvm.ptr -> i64
%955 = llvm.load %883 : !llvm.ptr -> i64
%956 = llvm.getelementptr %449[%955] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %954, %956 : i64, !llvm.ptr
cf.br ^bb188
^bb188:
%957 = llvm.load %458 : !llvm.ptr -> i64
%958 = llvm.load %839 : !llvm.ptr -> i64
%959 = llvm.load %909 : !llvm.ptr -> i64
%960 = arith.muli %958, %959 : i64
%961 = arith.addi %957, %960 : i64
llvm.store %961, %458 : i64, !llvm.ptr
cf.br ^bb179
^bb178:
cf.br ^bb179
^bb179:
%962 = llvm.load %828 : !llvm.ptr -> i64
%963 = arith.constant 1 : i32
%965 = arith.extsi %963 : i32 to i64
%964 = arith.addi %962, %965 : i64
llvm.store %964, %805 : i64, !llvm.ptr
cf.br ^bb162
^bb164:
cf.br ^bb161
^bb160:
cf.br ^bb161
^bb161:
cf.br ^bb158
^bb157:
cf.br ^bb158
^bb158:
%966 = llvm.load %474 : !llvm.ptr -> i64
%967 = arith.constant 1 : i32
%969 = arith.extsi %967 : i32 to i64
%968 = arith.addi %966, %969 : i64
llvm.store %968, %474 : i64, !llvm.ptr
cf.br ^bb153
^bb155:
%970 = llvm.load %596 : !llvm.ptr -> i64
%971 = arith.constant 1 : i32
%973 = arith.extsi %971 : i32 to i64
%972 = arith.addi %970, %973 : i64
llvm.store %972, %596 : i64, !llvm.ptr
cf.br ^bb147
^bb149:
%974 = llvm.mlir.addressof @str_0 : !llvm.ptr
%975 = llvm.load %458 : !llvm.ptr -> i64
%976 = llvm.call @printf(%974, %975) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%977 = arith.constant 0 : i32
func.return %977 : i32
}
}