← All problems Problem 541
Divisibility of Harmonic Number Denominators — M(137).
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^3)?Space complexity O(n^2)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 541
# Divisibility of Harmonic Number Denominators — M(137).
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const P: i64 = 137
const SMAX: i64 = 12
const CAP: i64 = 65536
function mulmod(a: i128, b: i128, mod: i128) -> i128 {
let mut result: i128 = 0
let mut x: i128 = a % mod
if x < 0 { x = x + mod }
let mut y: i128 = b % mod
if y < 0 { y = y + mod }
while y > 0 {
if (y & 1) != 0 {
result = result + x
if result >= mod { result = result - mod }
}
x = x + x
if x >= mod { x = x - mod }
y = y >> 1
}
return result
}
function modpow(b0: i128, e0: i64, mod: i128) -> i128 {
let mut r: i128 = 1
let mut b: i128 = b0 % mod
if b < 0 { b = b + mod }
let mut e: i64 = e0
while e > 0 {
if (e & 1) != 0 { r = mulmod(r, b, mod) }
b = mulmod(b, b, mod)
e = e >> 1
}
return r
}
function inv_mod(a0: i128, mod: i128) -> i128 {
let mut a: i128 = a0 % mod
if a < 0 { a = a + mod }
let mut t: i128 = 0
let mut newt: i128 = 1
let mut r: i128 = mod
let mut newr: i128 = a
while newr != 0 {
let q: i128 = r / newr
let tt: i128 = newt
let prod: i128 = mulmod(q, newt, mod)
newt = t - prod
if newt < 0 { newt = newt + mod }
t = tt
let rr: i128 = newr
newr = r - q * newr
r = rr
}
if r != 1 { return 0 }
if t < 0 { t = t + mod }
return t
}
function ipow_mod(b: i64, e: i64) -> i128 {
let mut r: i128 = 1 as i128
let mut base: i128 = b as i128
let mut exp: i64 = e
while exp > 0 {
if (exp & 1) != 0 { r = r * base }
base = base * base
exp = exp >> 1
}
return r
}
function hslot(k: i64, keys: ptr<i64>, used: ptr<i8>) -> i64 {
let mut h: i64 = k % CAP
if h < 0 { h = h + CAP }
while used[h] == 1 && keys[h] != k {
h = h + 1
if h == CAP { h = 0 }
}
return h
}
function pow_sum(m: i64, q: i64, s: i64,
binom: ptr<i64>, prefix: ptr<i128>, digit: ptr<i128>,
pk: ptr<i64>, pv: ptr<i128>, pu: ptr<i8>) -> i128 {
if q <= 0 { return 0 }
let key: i64 = m * 100000 + q * 100 + s
let slot: i64 = hslot(key, pk, pu)
if pu[slot] == 1 { return pv[slot] }
let modv: i128 = ipow_mod(P, s)
let mut res: i128 = 0
if q <= P {
res = prefix[q * (SMAX + 1) + m] % modv
} else {
let Q: i64 = q / P
let R: i64 = q % P
let mut t: i64 = 0
while t <= m {
let term: i128 = mulmod(mulmod(mulmod(
binom[m * (SMAX + 1) + t] as i128,
modpow(P as i128, t, modv), modv),
pow_sum(t, Q, s, binom, prefix, digit, pk, pv, pu), modv),
digit[m - t], modv)
res = res + term
if res >= modv { res = res - modv }
t = t + 1
}
let base: i128 = ((Q as i128) * (P as i128)) % modv
t = 0
while t <= m {
let term: i128 = mulmod(mulmod(
binom[m * (SMAX + 1) + t] as i128,
modpow(base, t, modv), modv),
prefix[R * (SMAX + 1) + (m - t)], modv)
res = res + term
if res >= modv { res = res - modv }
t = t + 1
}
}
pu[slot] = 1
pk[slot] = key
pv[slot] = res
return res
}
function get_cm(s: i64, m: i64, ck: ptr<i64>, cv: ptr<i128>, cu: ptr<i8>) -> i128 {
let key: i64 = s * 100 + m
let slot: i64 = hslot(key, ck, cu)
if cu[slot] == 1 { return cv[slot] }
let modv: i128 = ipow_mod(P, s)
let mut sm: i128 = 0
let mut j: i64 = 1
while j < P {
let invj: i128 = inv_mod(j as i128, modv)
sm = sm + modpow(invj, m + 1, modv)
if sm >= modv { sm = sm - modv }
j = j + 1
}
cu[slot] = 1
ck[slot] = key
cv[slot] = sm
return sm
}
function unit_inverse_sum(N: i64, s: i64,
binom: ptr<i64>, prefix: ptr<i128>, digit: ptr<i128>,
pk: ptr<i64>, pv: ptr<i128>, pu: ptr<i8>,
ck: ptr<i64>, cv: ptr<i128>, cu: ptr<i8>,
uk: ptr<i64>, uv: ptr<i128>, uu: ptr<i8>) -> i128 {
if N <= 0 { return 0 }
let key: i64 = N * 20 + s
let slot: i64 = hslot(key % CAP, uk, uu)
if uu[slot] == 1 && uk[slot] == key { return uv[slot] }
let modv: i128 = ipow_mod(P, s)
let q: i64 = N / P
let r: i64 = N % P
let mut total: i128 = 0
if q > 0 {
let mut m: i64 = 0
while m < s {
let Sm: i128 = pow_sum(m, q, s, binom, prefix, digit, pk, pv, pu)
let mut term: i128 = mulmod(modpow(P as i128, m, modv), Sm, modv)
term = mulmod(term, get_cm(s, m, ck, cv, cu), modv)
if (m & 1) != 0 { term = modv - term; if term >= modv { term = 0 } }
total = total + term
if total >= modv { total = total - modv }
m = m + 1
}
}
let base: i64 = q * P
let mut j: i64 = 1
while j <= r {
if j % P != 0 {
total = total + inv_mod((base + j) as i128, modv)
if total >= modv { total = total - modv }
}
j = j + 1
}
uu[slot] = 1
uk[slot] = key
uv[slot] = total
return total
}
function V_val(e: i64, m: i64, mp: i64,
binom: ptr<i64>, prefix: ptr<i128>, digit: ptr<i128>,
pk: ptr<i64>, pv: ptr<i128>, pu: ptr<i8>,
ck: ptr<i64>, cv: ptr<i128>, cu: ptr<i8>,
uk: ptr<i64>, uv: ptr<i128>, uu: ptr<i8>,
vk: ptr<i64>, vv: ptr<i128>, vu: ptr<i8>) -> i128 {
let key: i64 = e * 1000000000000000 + m * 1000 + mp
let slot: i64 = hslot(key % CAP, vk, vu)
if vu[slot] == 1 && vk[slot] == key { return vv[slot] }
let modv: i128 = ipow_mod(P, mp)
let mut val: i128 = 0
let mut div: i128 = 1
let mut t: i64 = 1
while t <= e {
let coeff: i128 = ipow_mod(P, e - t)
let N: i64 = ((m as i128) / div) as i64
val = val + mulmod(coeff, unit_inverse_sum(N, mp, binom, prefix, digit, pk, pv, pu, ck, cv, cu, uk, uv, uu), modv)
if val >= modv { val = val - modv }
div = div * (P as i128)
t = t + 1
}
vu[slot] = 1
vk[slot] = key
vv[slot] = val
return val
}
function main() -> i32 {
let binom: ptr<i64> = calloc((SMAX + 1) * (SMAX + 1), 8)
let prefix: ptr<i128> = calloc((P + 1) * (SMAX + 1), 16)
let digit: ptr<i128> = calloc(SMAX + 1, 16)
let ha_cnt: ptr<i64> = calloc(P, 8)
let ha_dig: ptr<i64> = calloc(P * P, 8)
if binom == null || prefix == null || digit == null || ha_cnt == null || ha_dig == null { return 1 }
let mut n: i64 = 0
while n <= SMAX {
binom[n * (SMAX + 1) + 0] = 1
binom[n * (SMAX + 1) + n] = 1
let mut k: i64 = 1
while k < n {
binom[n * (SMAX + 1) + k] = binom[(n - 1) * (SMAX + 1) + (k - 1)] + binom[(n - 1) * (SMAX + 1) + k]
k = k + 1
}
n = n + 1
}
let mut r: i64 = 1
while r <= P {
let b: i64 = r - 1
let mut k: i64 = 0
while k <= SMAX {
prefix[r * (SMAX + 1) + k] = prefix[(r - 1) * (SMAX + 1) + k] + ipow_mod(b, k)
k = k + 1
}
r = r + 1
}
let mut k: i64 = 0
while k <= SMAX {
digit[k] = prefix[P * (SMAX + 1) + k]
k = k + 1
}
let invs: ptr<i64> = calloc(P, 8)
let ha: ptr<i64> = calloc(P, 8)
if invs == null || ha == null { return 1 }
let mut a: i64 = 1
while a < P {
invs[a] = inv_mod(a as i128, P as i128) as i64
a = a + 1
}
let mut s: i64 = 0
a = 1
while a < P {
s = (s + invs[a]) % P
ha[a] = s
a = a + 1
}
ha[0] = 0
a = 0
while a < P {
let v: i64 = ha[a]
let idx: i64 = ha_cnt[v]
ha_dig[v * P + idx] = a
ha_cnt[v] = idx + 1
a = a + 1
}
let pk: ptr<i64> = calloc(CAP, 8)
let pv: ptr<i128> = calloc(CAP, 16)
let pu: ptr<i8> = calloc(CAP, 1)
let ck: ptr<i64> = calloc(CAP, 8)
let cv: ptr<i128> = calloc(CAP, 16)
let cu: ptr<i8> = calloc(CAP, 1)
let uk: ptr<i64> = calloc(CAP, 8)
let uv: ptr<i128> = calloc(CAP, 16)
let uu: ptr<i8> = calloc(CAP, 1)
let vk: ptr<i64> = calloc(CAP, 8)
let vv: ptr<i128> = calloc(CAP, 16)
let vu: ptr<i8> = calloc(CAP, 1)
let A: ptr<i64> = calloc(4096, 8)
let An: ptr<i64> = calloc(1, 8)
if pk == null || pv == null || pu == null { return 1 }
let mut best: i64 = P - 1
An[0] = 0
let mut i: i64 = 0
while i < ha_cnt[0] {
let m: i64 = ha_dig[0 * P + i]
if m >= 1 && m < P {
A[An[0]] = m
An[0] = An[0] + 1
}
i = i + 1
}
let mut e: i64 = 1
while An[0] > 0 {
let mut maxA: i64 = 0
i = 0
while i < An[0] {
if A[i] > maxA { maxA = A[i] }
i = i + 1
}
best = P * maxA + (P - 1)
let nextA: ptr<i64> = calloc(4096, 8)
let mut nn: i64 = 0
i = 0
while i < An[0] {
let q: i64 = A[i]
let val: i128 = V_val(e, q, e + 1, binom, prefix, digit, pk, pv, pu, ck, cv, cu, uk, uv, uu, vk, vv, vu)
let pe: i128 = ipow_mod(P, e)
let d: i64 = ((val / pe) % (P as i128)) as i64
let target: i64 = (P - d) % P
let mut j: i64 = 0
while j < ha_cnt[target] {
let digit_a: i64 = ha_dig[target * P + j]
let child: i64 = q * P + digit_a
let mut dup: i32 = 0
let mut t: i64 = 0
while t < nn {
if nextA[t] == child { dup = 1; break }
t = t + 1
}
if dup == 0 {
nextA[nn] = child
nn = nn + 1
}
j = j + 1
}
i = i + 1
}
i = 0
while i < nn { A[i] = nextA[i]; i = i + 1 }
An[0] = nn
free(nextA)
e = e + 1
if e > 30 { break }
}
printf("%lld\n", best)
free(binom); free(prefix); free(digit); free(ha_cnt); free(ha_dig)
free(invs); free(ha); free(pk); free(pv); free(pu)
free(ck); free(cv); free(cu); free(uk); free(uv); free(uu)
free(vk); free(vv); free(vu); free(A); free(An)
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; }
__int128 mulmod_i128_i128_i128(__int128 a, __int128 b, __int128 mod);
__int128 modpow_i128_i64_i128(__int128 b0, int64_t e0, __int128 mod);
__int128 inv_mod_i128_i128(__int128 a0, __int128 mod);
__int128 ipow_mod_i64_i64(int64_t b, int64_t e);
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t k, int64_t* keys, int8_t* used);
__int128 pow_sum_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8(int64_t m, int64_t q, int64_t s, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu);
__int128 get_cm_i64_i64_ptr_i64_ptr_i128_ptr_i8(int64_t s, int64_t m, int64_t* ck, __int128* cv, int8_t* cu);
__int128 unit_inverse_sum_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(int64_t N, int64_t s, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu, int64_t* ck, __int128* cv, int8_t* cu, int64_t* uk, __int128* uv, int8_t* uu);
__int128 V_val_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(int64_t e, int64_t m, int64_t mp, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu, int64_t* ck, __int128* cv, int8_t* cu, int64_t* uk, __int128* uv, int8_t* uu, int64_t* vk, __int128* vv, int8_t* vu);
int32_t main(void);
static const int64_t P = 137;
static const int64_t SMAX = 12;
static const int64_t CAP = 65536;
__int128 mulmod_i128_i128_i128(__int128 a, __int128 b, __int128 mod) {
__int128 result = 0;
__int128 x = FLOW_CHECKED_MOD((a), (mod));
if (x < 0) {
x = (x + mod);
}
__int128 y = FLOW_CHECKED_MOD((b), (mod));
if (y < 0) {
y = (y + mod);
}
while (y > 0) {
if ((y & 1) != 0) {
result = (result + x);
if (result >= mod) {
result = (result - mod);
}
}
x = (x + x);
if (x >= mod) {
x = (x - mod);
}
y = FLOW_CHECKED_SHR((y), (1));
}
return result;
}
__int128 modpow_i128_i64_i128(__int128 b0, int64_t e0, __int128 mod) {
__int128 r = 1;
__int128 b = FLOW_CHECKED_MOD((b0), (mod));
if (b < 0) {
b = (b + mod);
}
int64_t e = e0;
while (e > 0) {
if ((e & 1) != 0) {
r = mulmod_i128_i128_i128(r, b, mod);
}
b = mulmod_i128_i128_i128(b, b, mod);
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
__int128 inv_mod_i128_i128(__int128 a0, __int128 mod) {
__int128 a = FLOW_CHECKED_MOD((a0), (mod));
if (a < 0) {
a = (a + mod);
}
__int128 t = 0;
__int128 newt = 1;
__int128 r = mod;
__int128 newr = a;
while (newr != 0) {
__int128 q = FLOW_CHECKED_DIV((r), (newr));
__int128 tt = newt;
__int128 prod = mulmod_i128_i128_i128(q, newt, mod);
newt = (t - prod);
if (newt < 0) {
newt = (newt + mod);
}
t = tt;
__int128 rr = newr;
newr = (r - (q * newr));
r = rr;
}
if (r != 1) {
return 0;
}
if (t < 0) {
t = (t + mod);
}
return t;
}
__int128 ipow_mod_i64_i64(int64_t b, int64_t e) {
__int128 r = ((__int128)(1));
__int128 base = ((__int128)(b));
int64_t exp = e;
while (exp > 0) {
if ((exp & 1) != 0) {
r = (r * base);
}
base = (base * base);
exp = FLOW_CHECKED_SHR((exp), (1));
}
return r;
}
int64_t hslot_i64_ptr_i64_ptr_i8(int64_t k, int64_t* keys, int8_t* used) {
int64_t h = FLOW_CHECKED_MOD((k), (CAP));
if (h < 0) {
h = (h + CAP);
}
while ((used[h] == 1 && keys[h] != k)) {
h = (h + 1);
if (h == CAP) {
h = 0;
}
}
return h;
}
__int128 pow_sum_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8(int64_t m, int64_t q, int64_t s, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu) {
if (q <= 0) {
return 0;
}
int64_t key = (((m * 100000) + (q * 100)) + s);
int64_t slot = hslot_i64_ptr_i64_ptr_i8(key, pk, pu);
if (pu[slot] == 1) {
return pv[slot];
}
__int128 modv = ipow_mod_i64_i64(P, s);
__int128 res = 0;
if (q <= P) {
res = FLOW_CHECKED_MOD((prefix[((q * (SMAX + 1)) + m)]), (modv));
} else {
int64_t Q = FLOW_CHECKED_DIV((q), (P));
int64_t R = FLOW_CHECKED_MOD((q), (P));
int64_t t = 0;
while (t <= m) {
__int128 term = mulmod_i128_i128_i128(mulmod_i128_i128_i128(mulmod_i128_i128_i128(((__int128)(binom[((m * (SMAX + 1)) + t)])), modpow_i128_i64_i128(((__int128)(P)), t, modv), modv), pow_sum_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8(t, Q, s, binom, prefix, digit, pk, pv, pu), modv), digit[(m - t)], modv);
res = (res + term);
if (res >= modv) {
res = (res - modv);
}
t = (t + 1);
}
__int128 base = FLOW_CHECKED_MOD(((((__int128)(Q)) * ((__int128)(P)))), (modv));
t = 0;
while (t <= m) {
__int128 term = mulmod_i128_i128_i128(mulmod_i128_i128_i128(((__int128)(binom[((m * (SMAX + 1)) + t)])), modpow_i128_i64_i128(base, t, modv), modv), prefix[((R * (SMAX + 1)) + (m - t))], modv);
res = (res + term);
if (res >= modv) {
res = (res - modv);
}
t = (t + 1);
}
}
pu[slot] = 1;
pk[slot] = key;
pv[slot] = res;
return res;
}
__int128 get_cm_i64_i64_ptr_i64_ptr_i128_ptr_i8(int64_t s, int64_t m, int64_t* ck, __int128* cv, int8_t* cu) {
int64_t key = ((s * 100) + m);
int64_t slot = hslot_i64_ptr_i64_ptr_i8(key, ck, cu);
if (cu[slot] == 1) {
return cv[slot];
}
__int128 modv = ipow_mod_i64_i64(P, s);
__int128 sm = 0;
int64_t j = 1;
while (j < P) {
__int128 invj = inv_mod_i128_i128(((__int128)(j)), modv);
sm = (sm + modpow_i128_i64_i128(invj, (m + 1), modv));
if (sm >= modv) {
sm = (sm - modv);
}
j = (j + 1);
}
cu[slot] = 1;
ck[slot] = key;
cv[slot] = sm;
return sm;
}
__int128 unit_inverse_sum_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(int64_t N, int64_t s, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu, int64_t* ck, __int128* cv, int8_t* cu, int64_t* uk, __int128* uv, int8_t* uu) {
if (N <= 0) {
return 0;
}
int64_t key = ((N * 20) + s);
int64_t slot = hslot_i64_ptr_i64_ptr_i8(FLOW_CHECKED_MOD((key), (CAP)), uk, uu);
if ((uu[slot] == 1 && uk[slot] == key)) {
return uv[slot];
}
__int128 modv = ipow_mod_i64_i64(P, s);
int64_t q = FLOW_CHECKED_DIV((N), (P));
int64_t r = FLOW_CHECKED_MOD((N), (P));
__int128 total = 0;
if (q > 0) {
int64_t m = 0;
while (m < s) {
__int128 Sm = pow_sum_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8(m, q, s, binom, prefix, digit, pk, pv, pu);
__int128 term = mulmod_i128_i128_i128(modpow_i128_i64_i128(((__int128)(P)), m, modv), Sm, modv);
term = mulmod_i128_i128_i128(term, get_cm_i64_i64_ptr_i64_ptr_i128_ptr_i8(s, m, ck, cv, cu), modv);
if ((m & 1) != 0) {
term = (modv - term);
if (term >= modv) {
term = 0;
}
}
total = (total + term);
if (total >= modv) {
total = (total - modv);
}
m = (m + 1);
}
}
int64_t base = (q * P);
int64_t j = 1;
while (j <= r) {
if (FLOW_CHECKED_MOD((j), (P)) != 0) {
total = (total + inv_mod_i128_i128(((__int128)((base + j))), modv));
if (total >= modv) {
total = (total - modv);
}
}
j = (j + 1);
}
uu[slot] = 1;
uk[slot] = key;
uv[slot] = total;
return total;
}
__int128 V_val_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(int64_t e, int64_t m, int64_t mp, int64_t* binom, __int128* prefix, __int128* digit, int64_t* pk, __int128* pv, int8_t* pu, int64_t* ck, __int128* cv, int8_t* cu, int64_t* uk, __int128* uv, int8_t* uu, int64_t* vk, __int128* vv, int8_t* vu) {
int64_t key = (((e * 1000000000000000) + (m * 1000)) + mp);
int64_t slot = hslot_i64_ptr_i64_ptr_i8(FLOW_CHECKED_MOD((key), (CAP)), vk, vu);
if ((vu[slot] == 1 && vk[slot] == key)) {
return vv[slot];
}
__int128 modv = ipow_mod_i64_i64(P, mp);
__int128 val = 0;
__int128 div = 1;
int64_t t = 1;
while (t <= e) {
__int128 coeff = ipow_mod_i64_i64(P, (e - t));
int64_t N = ((int64_t)(FLOW_CHECKED_DIV((((__int128)(m))), (div))));
val = (val + mulmod_i128_i128_i128(coeff, unit_inverse_sum_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(N, mp, binom, prefix, digit, pk, pv, pu, ck, cv, cu, uk, uv, uu), modv));
if (val >= modv) {
val = (val - modv);
}
div = (div * ((__int128)(P)));
t = (t + 1);
}
vu[slot] = 1;
vk[slot] = key;
vv[slot] = val;
return val;
}
int32_t main(void) {
int64_t* binom = (int64_t*)(calloc(((SMAX + 1) * (SMAX + 1)), 8));
__int128* prefix = (__int128*)(calloc(((P + 1) * (SMAX + 1)), 16));
__int128* digit = (__int128*)(calloc((SMAX + 1), 16));
int64_t* ha_cnt = (int64_t*)(calloc(P, 8));
int64_t* ha_dig = (int64_t*)(calloc((P * P), 8));
if (((((binom == NULL || prefix == NULL) || digit == NULL) || ha_cnt == NULL) || ha_dig == NULL)) {
return 1;
}
int64_t n = 0;
while (n <= SMAX) {
binom[((n * (SMAX + 1)) + 0)] = 1;
binom[((n * (SMAX + 1)) + n)] = 1;
int64_t k = 1;
while (k < n) {
binom[((n * (SMAX + 1)) + k)] = (binom[(((n - 1) * (SMAX + 1)) + (k - 1))] + binom[(((n - 1) * (SMAX + 1)) + k)]);
k = (k + 1);
}
n = (n + 1);
}
int64_t r = 1;
while (r <= P) {
int64_t b = (r - 1);
int64_t k = 0;
while (k <= SMAX) {
prefix[((r * (SMAX + 1)) + k)] = (prefix[(((r - 1) * (SMAX + 1)) + k)] + ipow_mod_i64_i64(b, k));
k = (k + 1);
}
r = (r + 1);
}
int64_t k = 0;
while (k <= SMAX) {
digit[k] = prefix[((P * (SMAX + 1)) + k)];
k = (k + 1);
}
int64_t* invs = (int64_t*)(calloc(P, 8));
int64_t* ha = (int64_t*)(calloc(P, 8));
if ((invs == NULL || ha == NULL)) {
return 1;
}
int64_t a = 1;
while (a < P) {
invs[a] = ((int64_t)(inv_mod_i128_i128(((__int128)(a)), ((__int128)(P)))));
a = (a + 1);
}
int64_t s = 0;
a = 1;
while (a < P) {
s = FLOW_CHECKED_MOD(((s + invs[a])), (P));
ha[a] = s;
a = (a + 1);
}
ha[0] = 0;
a = 0;
while (a < P) {
int64_t v = ha[a];
int64_t idx = ha_cnt[v];
ha_dig[((v * P) + idx)] = a;
ha_cnt[v] = (idx + 1);
a = (a + 1);
}
int64_t* pk = (int64_t*)(calloc(CAP, 8));
__int128* pv = (__int128*)(calloc(CAP, 16));
int8_t* pu = (int8_t*)(calloc(CAP, 1));
int64_t* ck = (int64_t*)(calloc(CAP, 8));
__int128* cv = (__int128*)(calloc(CAP, 16));
int8_t* cu = (int8_t*)(calloc(CAP, 1));
int64_t* uk = (int64_t*)(calloc(CAP, 8));
__int128* uv = (__int128*)(calloc(CAP, 16));
int8_t* uu = (int8_t*)(calloc(CAP, 1));
int64_t* vk = (int64_t*)(calloc(CAP, 8));
__int128* vv = (__int128*)(calloc(CAP, 16));
int8_t* vu = (int8_t*)(calloc(CAP, 1));
int64_t* A = (int64_t*)(calloc(4096, 8));
int64_t* An = (int64_t*)(calloc(1, 8));
if (((pk == NULL || pv == NULL) || pu == NULL)) {
return 1;
}
int64_t best = (P - 1);
An[0] = 0;
int64_t i = 0;
while (i < ha_cnt[0]) {
int64_t m = ha_dig[((0 * P) + i)];
if ((m >= 1 && m < P)) {
A[An[0]] = m;
An[0] = (An[0] + 1);
}
i = (i + 1);
}
int64_t e = 1;
while (An[0] > 0) {
int64_t maxA = 0;
i = 0;
while (i < An[0]) {
if (A[i] > maxA) {
maxA = A[i];
}
i = (i + 1);
}
best = ((P * maxA) + (P - 1));
int64_t* nextA = (int64_t*)(calloc(4096, 8));
int64_t nn = 0;
i = 0;
while (i < An[0]) {
int64_t q = A[i];
__int128 val = V_val_i64_i64_i64_ptr_i64_ptr_i128_ptr_i128_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8_ptr_i64_ptr_i128_ptr_i8(e, q, (e + 1), binom, prefix, digit, pk, pv, pu, ck, cv, cu, uk, uv, uu, vk, vv, vu);
__int128 pe = ipow_mod_i64_i64(P, e);
int64_t d = ((int64_t)(FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((val), (pe))), (((__int128)(P))))));
int64_t target = FLOW_CHECKED_MOD(((P - d)), (P));
int64_t j = 0;
while (j < ha_cnt[target]) {
int64_t digit_a = ha_dig[((target * P) + j)];
int64_t child = ((q * P) + digit_a);
int32_t dup = 0;
int64_t t = 0;
while (t < nn) {
if (nextA[t] == child) {
dup = 1;
break;
}
t = (t + 1);
}
if (dup == 0) {
nextA[nn] = child;
nn = (nn + 1);
}
j = (j + 1);
}
i = (i + 1);
}
i = 0;
while (i < nn) {
A[i] = nextA[i];
i = (i + 1);
}
An[0] = nn;
free(nextA);
e = (e + 1);
if (e > 30) {
break;
}
}
printf("%lld\n", best);
free(binom);
free(prefix);
free(digit);
free(ha_cnt);
free(ha_dig);
free(invs);
free(ha);
free(pk);
free(pv);
free(pu);
free(ck);
free(cv);
free(cu);
free(uk);
free(uv);
free(uu);
free(vk);
free(vv);
free(vu);
free(A);
free(An);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: P
llvm.mlir.global internal constant @P(137 : i64) : i64
// Constant: SMAX
llvm.mlir.global internal constant @SMAX(12 : i64) : i64
// Constant: CAP
llvm.mlir.global internal constant @CAP(65536 : i64) : i64
func.func @mulmod(%arg0: i128, %arg1: i128, %arg2: i128) -> i128 {
%0 = arith.constant 0 : i32
%1 = arith.extsi %0 : i32 to i128
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i128 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i128, !llvm.ptr
%5 = arith.trunci %arg0 : i128 to i64
%6 = arith.trunci %arg2 : i128 to i64
%4 = arith.remsi %5, %6 : i64
%7 = arith.extsi %4 : i64 to i128
%8 = llvm.mlir.constant(1 : i64) : i64
%9 = llvm.alloca %8 x i128 : (i64) -> !llvm.ptr
llvm.store %7, %9 : i128, !llvm.ptr
%10 = llvm.load %9 : !llvm.ptr -> i128
%11 = arith.constant 0 : i32
%13 = arith.trunci %10 : i128 to i64
%14 = arith.extsi %11 : i32 to i64
%12 = arith.cmpi slt, %13, %14 : i64
cf.cond_br %12, ^bb0, ^bb1
^bb0:
%15 = llvm.load %9 : !llvm.ptr -> i128
%17 = arith.trunci %15 : i128 to i64
%18 = arith.trunci %arg2 : i128 to i64
%16 = arith.addi %17, %18 : i64
%19 = arith.extsi %16 : i64 to i128
llvm.store %19, %9 : i128, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%21 = arith.trunci %arg1 : i128 to i64
%22 = arith.trunci %arg2 : i128 to i64
%20 = arith.remsi %21, %22 : i64
%23 = arith.extsi %20 : i64 to i128
%24 = llvm.mlir.constant(1 : i64) : i64
%25 = llvm.alloca %24 x i128 : (i64) -> !llvm.ptr
llvm.store %23, %25 : i128, !llvm.ptr
%26 = llvm.load %25 : !llvm.ptr -> i128
%27 = arith.constant 0 : i32
%29 = arith.trunci %26 : i128 to i64
%30 = arith.extsi %27 : i32 to i64
%28 = arith.cmpi slt, %29, %30 : i64
cf.cond_br %28, ^bb3, ^bb4
^bb3:
%31 = llvm.load %25 : !llvm.ptr -> i128
%33 = arith.trunci %31 : i128 to i64
%34 = arith.trunci %arg2 : i128 to i64
%32 = arith.addi %33, %34 : i64
%35 = arith.extsi %32 : i64 to i128
llvm.store %35, %25 : i128, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
cf.br ^bb6
^bb6:
%36 = llvm.load %25 : !llvm.ptr -> i128
%37 = arith.constant 0 : i32
%39 = arith.trunci %36 : i128 to i64
%40 = arith.extsi %37 : i32 to i64
%38 = arith.cmpi sgt, %39, %40 : i64
cf.cond_br %38, ^bb7, ^bb8
^bb7:
%41 = llvm.load %25 : !llvm.ptr -> i128
%42 = arith.constant 1 : i32
%44 = arith.trunci %41 : i128 to i64
%45 = arith.extsi %42 : i32 to i64
%43 = arith.andi %44, %45 : i64
%46 = arith.constant 0 : i32
%48 = arith.extsi %46 : i32 to i64
%47 = arith.cmpi ne, %43, %48 : i64
cf.cond_br %47, ^bb9, ^bb10
^bb9:
%49 = llvm.load %3 : !llvm.ptr -> i128
%50 = llvm.load %9 : !llvm.ptr -> i128
%52 = arith.trunci %49 : i128 to i64
%53 = arith.trunci %50 : i128 to i64
%51 = arith.addi %52, %53 : i64
%54 = arith.extsi %51 : i64 to i128
llvm.store %54, %3 : i128, !llvm.ptr
%55 = llvm.load %3 : !llvm.ptr -> i128
%57 = arith.trunci %55 : i128 to i64
%58 = arith.trunci %arg2 : i128 to i64
%56 = arith.cmpi sge, %57, %58 : i64
cf.cond_br %56, ^bb12, ^bb13
^bb12:
%59 = llvm.load %3 : !llvm.ptr -> i128
%61 = arith.trunci %59 : i128 to i64
%62 = arith.trunci %arg2 : i128 to i64
%60 = arith.subi %61, %62 : i64
%63 = arith.extsi %60 : i64 to i128
llvm.store %63, %3 : i128, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%64 = llvm.load %9 : !llvm.ptr -> i128
%65 = llvm.load %9 : !llvm.ptr -> i128
%67 = arith.trunci %64 : i128 to i64
%68 = arith.trunci %65 : i128 to i64
%66 = arith.addi %67, %68 : i64
%69 = arith.extsi %66 : i64 to i128
llvm.store %69, %9 : i128, !llvm.ptr
%70 = llvm.load %9 : !llvm.ptr -> i128
%72 = arith.trunci %70 : i128 to i64
%73 = arith.trunci %arg2 : i128 to i64
%71 = arith.cmpi sge, %72, %73 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%74 = llvm.load %9 : !llvm.ptr -> i128
%76 = arith.trunci %74 : i128 to i64
%77 = arith.trunci %arg2 : i128 to i64
%75 = arith.subi %76, %77 : i64
%78 = arith.extsi %75 : i64 to i128
llvm.store %78, %9 : i128, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%79 = llvm.load %25 : !llvm.ptr -> i128
%80 = arith.constant 1 : i32
%82 = arith.trunci %79 : i128 to i64
%83 = arith.extsi %80 : i32 to i64
%81 = arith.shrsi %82, %83 : i64
%84 = arith.extsi %81 : i64 to i128
llvm.store %84, %25 : i128, !llvm.ptr
cf.br ^bb6
^bb8:
%85 = llvm.load %3 : !llvm.ptr -> i128
func.return %85 : i128
}
func.func @modpow(%arg0: i128, %arg1: i64, %arg2: i128) -> i128 {
%86 = arith.constant 1 : i32
%87 = arith.extsi %86 : i32 to i128
%88 = llvm.mlir.constant(1 : i64) : i64
%89 = llvm.alloca %88 x i128 : (i64) -> !llvm.ptr
llvm.store %87, %89 : i128, !llvm.ptr
%91 = arith.trunci %arg0 : i128 to i64
%92 = arith.trunci %arg2 : i128 to i64
%90 = arith.remsi %91, %92 : i64
%93 = arith.extsi %90 : i64 to i128
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i128 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i128, !llvm.ptr
%96 = llvm.load %95 : !llvm.ptr -> i128
%97 = arith.constant 0 : i32
%99 = arith.trunci %96 : i128 to i64
%100 = arith.extsi %97 : i32 to i64
%98 = arith.cmpi slt, %99, %100 : i64
cf.cond_br %98, ^bb18, ^bb19
^bb18:
%101 = llvm.load %95 : !llvm.ptr -> i128
%103 = arith.trunci %101 : i128 to i64
%104 = arith.trunci %arg2 : i128 to i64
%102 = arith.addi %103, %104 : i64
%105 = arith.extsi %102 : i64 to i128
llvm.store %105, %95 : i128, !llvm.ptr
cf.br ^bb20
^bb19:
cf.br ^bb20
^bb20:
%106 = llvm.mlir.constant(1 : i64) : i64
%107 = llvm.alloca %106 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %107 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%108 = llvm.load %107 : !llvm.ptr -> i64
%109 = arith.constant 0 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi sgt, %108, %111 : i64
cf.cond_br %110, ^bb22, ^bb23
^bb22:
%112 = llvm.load %107 : !llvm.ptr -> i64
%113 = arith.constant 1 : i32
%115 = arith.extsi %113 : i32 to i64
%114 = arith.andi %112, %115 : i64
%116 = arith.constant 0 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.cmpi ne, %114, %118 : i64
cf.cond_br %117, ^bb24, ^bb25
^bb24:
%120 = llvm.load %89 : !llvm.ptr -> i128
%121 = llvm.load %95 : !llvm.ptr -> i128
%119 = func.call @mulmod(%120, %121, %arg2) : (i128, i128, i128) -> i128
llvm.store %119, %89 : i128, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%123 = llvm.load %95 : !llvm.ptr -> i128
%124 = llvm.load %95 : !llvm.ptr -> i128
%122 = func.call @mulmod(%123, %124, %arg2) : (i128, i128, i128) -> i128
llvm.store %122, %95 : i128, !llvm.ptr
%125 = llvm.load %107 : !llvm.ptr -> i64
%126 = arith.constant 1 : i32
%128 = arith.extsi %126 : i32 to i64
%127 = arith.shrsi %125, %128 : i64
llvm.store %127, %107 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%129 = llvm.load %89 : !llvm.ptr -> i128
func.return %129 : i128
}
func.func @inv_mod(%arg0: i128, %arg1: i128) -> i128 {
%131 = arith.trunci %arg0 : i128 to i64
%132 = arith.trunci %arg1 : i128 to i64
%130 = arith.remsi %131, %132 : i64
%133 = arith.extsi %130 : i64 to i128
%134 = llvm.mlir.constant(1 : i64) : i64
%135 = llvm.alloca %134 x i128 : (i64) -> !llvm.ptr
llvm.store %133, %135 : i128, !llvm.ptr
%136 = llvm.load %135 : !llvm.ptr -> i128
%137 = arith.constant 0 : i32
%139 = arith.trunci %136 : i128 to i64
%140 = arith.extsi %137 : i32 to i64
%138 = arith.cmpi slt, %139, %140 : i64
cf.cond_br %138, ^bb27, ^bb28
^bb27:
%141 = llvm.load %135 : !llvm.ptr -> i128
%143 = arith.trunci %141 : i128 to i64
%144 = arith.trunci %arg1 : i128 to i64
%142 = arith.addi %143, %144 : i64
%145 = arith.extsi %142 : i64 to i128
llvm.store %145, %135 : i128, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%146 = arith.constant 0 : i32
%147 = arith.extsi %146 : i32 to i128
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i128 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i128, !llvm.ptr
%150 = arith.constant 1 : i32
%151 = arith.extsi %150 : i32 to i128
%152 = llvm.mlir.constant(1 : i64) : i64
%153 = llvm.alloca %152 x i128 : (i64) -> !llvm.ptr
llvm.store %151, %153 : i128, !llvm.ptr
%154 = llvm.mlir.constant(1 : i64) : i64
%155 = llvm.alloca %154 x i128 : (i64) -> !llvm.ptr
llvm.store %arg1, %155 : i128, !llvm.ptr
%156 = llvm.load %135 : !llvm.ptr -> i128
%157 = llvm.mlir.constant(1 : i64) : i64
%158 = llvm.alloca %157 x i128 : (i64) -> !llvm.ptr
llvm.store %156, %158 : i128, !llvm.ptr
cf.br ^bb30
^bb30:
%159 = llvm.load %158 : !llvm.ptr -> i128
%160 = arith.constant 0 : i32
%162 = arith.trunci %159 : i128 to i64
%163 = arith.extsi %160 : i32 to i64
%161 = arith.cmpi ne, %162, %163 : i64
cf.cond_br %161, ^bb31, ^bb32
^bb31:
%164 = llvm.load %155 : !llvm.ptr -> i128
%165 = llvm.load %158 : !llvm.ptr -> i128
%167 = arith.trunci %164 : i128 to i64
%168 = arith.trunci %165 : i128 to i64
%166 = arith.divsi %167, %168 : i64
%169 = arith.extsi %166 : i64 to i128
%170 = llvm.load %153 : !llvm.ptr -> i128
%172 = llvm.load %153 : !llvm.ptr -> i128
%171 = func.call @mulmod(%169, %172, %arg1) : (i128, i128, i128) -> i128
%173 = llvm.load %149 : !llvm.ptr -> i128
%175 = arith.trunci %173 : i128 to i64
%176 = arith.trunci %171 : i128 to i64
%174 = arith.subi %175, %176 : i64
%177 = arith.extsi %174 : i64 to i128
llvm.store %177, %153 : i128, !llvm.ptr
%178 = llvm.load %153 : !llvm.ptr -> i128
%179 = arith.constant 0 : i32
%181 = arith.trunci %178 : i128 to i64
%182 = arith.extsi %179 : i32 to i64
%180 = arith.cmpi slt, %181, %182 : i64
cf.cond_br %180, ^bb33, ^bb34
^bb33:
%183 = llvm.load %153 : !llvm.ptr -> i128
%185 = arith.trunci %183 : i128 to i64
%186 = arith.trunci %arg1 : i128 to i64
%184 = arith.addi %185, %186 : i64
%187 = arith.extsi %184 : i64 to i128
llvm.store %187, %153 : i128, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
llvm.store %170, %149 : i128, !llvm.ptr
%188 = llvm.load %158 : !llvm.ptr -> i128
%189 = llvm.load %155 : !llvm.ptr -> i128
%190 = llvm.load %158 : !llvm.ptr -> i128
%192 = arith.trunci %169 : i128 to i64
%193 = arith.trunci %190 : i128 to i64
%191 = arith.muli %192, %193 : i64
%195 = arith.trunci %189 : i128 to i64
%194 = arith.subi %195, %191 : i64
%196 = arith.extsi %194 : i64 to i128
llvm.store %196, %158 : i128, !llvm.ptr
llvm.store %188, %155 : i128, !llvm.ptr
cf.br ^bb30
^bb32:
%197 = llvm.load %155 : !llvm.ptr -> i128
%198 = arith.constant 1 : i32
%200 = arith.trunci %197 : i128 to i64
%201 = arith.extsi %198 : i32 to i64
%199 = arith.cmpi ne, %200, %201 : i64
cf.cond_br %199, ^bb36, ^bb37
^bb36:
%202 = arith.constant 0 : i32
%203 = arith.extsi %202 : i32 to i128
func.return %203 : i128
^bb37:
cf.br ^bb38
^bb38:
%204 = llvm.load %149 : !llvm.ptr -> i128
%205 = arith.constant 0 : i32
%207 = arith.trunci %204 : i128 to i64
%208 = arith.extsi %205 : i32 to i64
%206 = arith.cmpi slt, %207, %208 : i64
cf.cond_br %206, ^bb39, ^bb40
^bb39:
%209 = llvm.load %149 : !llvm.ptr -> i128
%211 = arith.trunci %209 : i128 to i64
%212 = arith.trunci %arg1 : i128 to i64
%210 = arith.addi %211, %212 : i64
%213 = arith.extsi %210 : i64 to i128
llvm.store %213, %149 : i128, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%214 = llvm.load %149 : !llvm.ptr -> i128
func.return %214 : i128
}
func.func @ipow_mod(%arg0: i64, %arg1: i64) -> i128 {
%215 = arith.constant 1 : i32
%216 = arith.extsi %215 : i32 to i128
%217 = llvm.mlir.constant(1 : i64) : i64
%218 = llvm.alloca %217 x i128 : (i64) -> !llvm.ptr
llvm.store %216, %218 : i128, !llvm.ptr
%219 = arith.extsi %arg0 : i64 to i128
%220 = llvm.mlir.constant(1 : i64) : i64
%221 = llvm.alloca %220 x i128 : (i64) -> !llvm.ptr
llvm.store %219, %221 : i128, !llvm.ptr
%222 = llvm.mlir.constant(1 : i64) : i64
%223 = llvm.alloca %222 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %223 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%224 = llvm.load %223 : !llvm.ptr -> i64
%225 = arith.constant 0 : i32
%227 = arith.extsi %225 : i32 to i64
%226 = arith.cmpi sgt, %224, %227 : i64
cf.cond_br %226, ^bb43, ^bb44
^bb43:
%228 = llvm.load %223 : !llvm.ptr -> i64
%229 = arith.constant 1 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.andi %228, %231 : i64
%232 = arith.constant 0 : i32
%234 = arith.extsi %232 : i32 to i64
%233 = arith.cmpi ne, %230, %234 : i64
cf.cond_br %233, ^bb45, ^bb46
^bb45:
%235 = llvm.load %218 : !llvm.ptr -> i128
%236 = llvm.load %221 : !llvm.ptr -> i128
%238 = arith.trunci %235 : i128 to i64
%239 = arith.trunci %236 : i128 to i64
%237 = arith.muli %238, %239 : i64
%240 = arith.extsi %237 : i64 to i128
llvm.store %240, %218 : i128, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%241 = llvm.load %221 : !llvm.ptr -> i128
%242 = llvm.load %221 : !llvm.ptr -> i128
%244 = arith.trunci %241 : i128 to i64
%245 = arith.trunci %242 : i128 to i64
%243 = arith.muli %244, %245 : i64
%246 = arith.extsi %243 : i64 to i128
llvm.store %246, %221 : i128, !llvm.ptr
%247 = llvm.load %223 : !llvm.ptr -> i64
%248 = arith.constant 1 : i32
%250 = arith.extsi %248 : i32 to i64
%249 = arith.shrsi %247, %250 : i64
llvm.store %249, %223 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%251 = llvm.load %218 : !llvm.ptr -> i128
func.return %251 : i128
}
func.func @hslot(%arg0: i64, %arg1: !llvm.ptr, %arg2: !llvm.ptr) -> i64 {
%252 = llvm.mlir.addressof @CAP : !llvm.ptr
%253 = llvm.load %252 : !llvm.ptr -> i64
%254 = arith.remsi %arg0, %253 : i64
%255 = llvm.mlir.constant(1 : i64) : i64
%256 = llvm.alloca %255 x i64 : (i64) -> !llvm.ptr
llvm.store %254, %256 : i64, !llvm.ptr
%257 = llvm.load %256 : !llvm.ptr -> i64
%258 = arith.constant 0 : i32
%260 = arith.extsi %258 : i32 to i64
%259 = arith.cmpi slt, %257, %260 : i64
cf.cond_br %259, ^bb48, ^bb49
^bb48:
%261 = llvm.load %256 : !llvm.ptr -> i64
%262 = llvm.mlir.addressof @CAP : !llvm.ptr
%263 = llvm.load %262 : !llvm.ptr -> i64
%264 = arith.addi %261, %263 : i64
llvm.store %264, %256 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
cf.br ^bb51
^bb51:
%266 = llvm.load %256 : !llvm.ptr -> i64
%267 = llvm.getelementptr %arg2[%266] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%265 = llvm.load %267 : !llvm.ptr -> i8
%268 = arith.constant 1 : i32
%270 = arith.extsi %265 : i8 to i32
%269 = arith.cmpi eq, %270, %268 : i32
%271 = scf.if %269 -> (i1) {
%273 = llvm.load %256 : !llvm.ptr -> i64
%274 = llvm.getelementptr %arg1[%273] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%272 = llvm.load %274 : !llvm.ptr -> i64
%275 = arith.cmpi ne, %272, %arg0 : i64
scf.yield %275 : i1
} else {
%276 = arith.constant false
scf.yield %276 : i1
}
cf.cond_br %271, ^bb52, ^bb53
^bb52:
%277 = llvm.load %256 : !llvm.ptr -> i64
%278 = arith.constant 1 : i32
%280 = arith.extsi %278 : i32 to i64
%279 = arith.addi %277, %280 : i64
llvm.store %279, %256 : i64, !llvm.ptr
%281 = llvm.load %256 : !llvm.ptr -> i64
%282 = llvm.mlir.addressof @CAP : !llvm.ptr
%283 = llvm.load %282 : !llvm.ptr -> i64
%284 = arith.cmpi eq, %281, %283 : i64
cf.cond_br %284, ^bb54, ^bb55
^bb54:
%285 = arith.constant 0 : i32
%286 = arith.extsi %285 : i32 to i64
llvm.store %286, %256 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
cf.br ^bb51
^bb53:
%287 = llvm.load %256 : !llvm.ptr -> i64
func.return %287 : i64
}
func.func @pow_sum(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr) -> i128 {
%288 = arith.constant 0 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.cmpi sle, %arg1, %290 : i64
cf.cond_br %289, ^bb57, ^bb58
^bb57:
%291 = arith.constant 0 : i32
%292 = arith.extsi %291 : i32 to i128
func.return %292 : i128
^bb58:
cf.br ^bb59
^bb59:
%293 = arith.constant 100000 : i32
%295 = arith.extsi %293 : i32 to i64
%294 = arith.muli %arg0, %295 : i64
%296 = arith.constant 100 : i32
%298 = arith.extsi %296 : i32 to i64
%297 = arith.muli %arg1, %298 : i64
%299 = arith.addi %294, %297 : i64
%300 = arith.addi %299, %arg2 : i64
%301 = func.call @hslot(%300, %arg6, %arg8) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%303 = llvm.getelementptr %arg8[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%302 = llvm.load %303 : !llvm.ptr -> i8
%304 = arith.constant 1 : i32
%306 = arith.extsi %302 : i8 to i32
%305 = arith.cmpi eq, %306, %304 : i32
cf.cond_br %305, ^bb60, ^bb61
^bb60:
%308 = llvm.getelementptr %arg7[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%307 = llvm.load %308 : !llvm.ptr -> i128
func.return %307 : i128
^bb61:
cf.br ^bb62
^bb62:
%310 = llvm.mlir.addressof @P : !llvm.ptr
%311 = llvm.load %310 : !llvm.ptr -> i64
%309 = func.call @ipow_mod(%311, %arg2) : (i64, i64) -> i128
%312 = arith.constant 0 : i32
%313 = arith.extsi %312 : i32 to i128
%314 = llvm.mlir.constant(1 : i64) : i64
%315 = llvm.alloca %314 x i128 : (i64) -> !llvm.ptr
llvm.store %313, %315 : i128, !llvm.ptr
%316 = llvm.mlir.addressof @P : !llvm.ptr
%317 = llvm.load %316 : !llvm.ptr -> i64
%318 = arith.cmpi sle, %arg1, %317 : i64
cf.cond_br %318, ^bb63, ^bb64
^bb63:
%320 = llvm.mlir.addressof @SMAX : !llvm.ptr
%321 = llvm.load %320 : !llvm.ptr -> i64
%322 = arith.constant 1 : i32
%324 = arith.extsi %322 : i32 to i64
%323 = arith.addi %321, %324 : i64
%325 = arith.muli %arg1, %323 : i64
%326 = arith.addi %325, %arg0 : i64
%327 = llvm.getelementptr %arg4[%326] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%319 = llvm.load %327 : !llvm.ptr -> i128
%329 = arith.trunci %319 : i128 to i64
%330 = arith.trunci %309 : i128 to i64
%328 = arith.remsi %329, %330 : i64
%331 = arith.extsi %328 : i64 to i128
llvm.store %331, %315 : i128, !llvm.ptr
cf.br ^bb65
^bb64:
%332 = llvm.mlir.addressof @P : !llvm.ptr
%333 = llvm.load %332 : !llvm.ptr -> i64
%334 = arith.divsi %arg1, %333 : i64
%335 = llvm.mlir.addressof @P : !llvm.ptr
%336 = llvm.load %335 : !llvm.ptr -> i64
%337 = arith.remsi %arg1, %336 : 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
cf.br ^bb66
^bb66:
%342 = llvm.load %341 : !llvm.ptr -> i64
%343 = arith.cmpi sle, %342, %arg0 : i64
cf.cond_br %343, ^bb67, ^bb68
^bb67:
%348 = llvm.mlir.addressof @SMAX : !llvm.ptr
%349 = llvm.load %348 : !llvm.ptr -> i64
%350 = arith.constant 1 : i32
%352 = arith.extsi %350 : i32 to i64
%351 = arith.addi %349, %352 : i64
%353 = arith.muli %arg0, %351 : i64
%354 = llvm.load %341 : !llvm.ptr -> i64
%355 = arith.addi %353, %354 : i64
%356 = llvm.getelementptr %arg3[%355] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%347 = llvm.load %356 : !llvm.ptr -> i64
%357 = arith.extsi %347 : i64 to i128
%359 = llvm.mlir.addressof @P : !llvm.ptr
%360 = llvm.load %359 : !llvm.ptr -> i64
%361 = arith.extsi %360 : i64 to i128
%362 = llvm.load %341 : !llvm.ptr -> i64
%358 = func.call @modpow(%361, %362, %309) : (i128, i64, i128) -> i128
%346 = func.call @mulmod(%357, %358, %309) : (i128, i128, i128) -> i128
%364 = llvm.load %341 : !llvm.ptr -> i64
%363 = func.call @pow_sum(%364, %334, %arg2, %arg3, %arg4, %arg5, %arg6, %arg7, %arg8) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i128
%345 = func.call @mulmod(%346, %363, %309) : (i128, i128, i128) -> i128
%366 = llvm.load %341 : !llvm.ptr -> i64
%367 = arith.subi %arg0, %366 : i64
%368 = llvm.getelementptr %arg5[%367] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%365 = llvm.load %368 : !llvm.ptr -> i128
%344 = func.call @mulmod(%345, %365, %309) : (i128, i128, i128) -> i128
%369 = llvm.load %315 : !llvm.ptr -> i128
%371 = arith.trunci %369 : i128 to i64
%372 = arith.trunci %344 : i128 to i64
%370 = arith.addi %371, %372 : i64
%373 = arith.extsi %370 : i64 to i128
llvm.store %373, %315 : i128, !llvm.ptr
%374 = llvm.load %315 : !llvm.ptr -> i128
%376 = arith.trunci %374 : i128 to i64
%377 = arith.trunci %309 : i128 to i64
%375 = arith.cmpi sge, %376, %377 : i64
cf.cond_br %375, ^bb69, ^bb70
^bb69:
%378 = llvm.load %315 : !llvm.ptr -> i128
%380 = arith.trunci %378 : i128 to i64
%381 = arith.trunci %309 : i128 to i64
%379 = arith.subi %380, %381 : i64
%382 = arith.extsi %379 : i64 to i128
llvm.store %382, %315 : i128, !llvm.ptr
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%383 = llvm.load %341 : !llvm.ptr -> i64
%384 = arith.constant 1 : i32
%386 = arith.extsi %384 : i32 to i64
%385 = arith.addi %383, %386 : i64
llvm.store %385, %341 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%387 = arith.extsi %334 : i64 to i128
%388 = llvm.mlir.addressof @P : !llvm.ptr
%389 = llvm.load %388 : !llvm.ptr -> i64
%390 = arith.extsi %389 : i64 to i128
%392 = arith.trunci %387 : i128 to i64
%393 = arith.trunci %390 : i128 to i64
%391 = arith.muli %392, %393 : i64
%395 = arith.trunci %309 : i128 to i64
%394 = arith.remsi %391, %395 : i64
%396 = arith.extsi %394 : i64 to i128
%397 = arith.constant 0 : i32
%398 = arith.extsi %397 : i32 to i64
llvm.store %398, %341 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%399 = llvm.load %341 : !llvm.ptr -> i64
%400 = arith.cmpi sle, %399, %arg0 : i64
cf.cond_br %400, ^bb73, ^bb74
^bb73:
%404 = llvm.mlir.addressof @SMAX : !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> i64
%406 = arith.constant 1 : i32
%408 = arith.extsi %406 : i32 to i64
%407 = arith.addi %405, %408 : i64
%409 = arith.muli %arg0, %407 : i64
%410 = llvm.load %341 : !llvm.ptr -> i64
%411 = arith.addi %409, %410 : i64
%412 = llvm.getelementptr %arg3[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%403 = llvm.load %412 : !llvm.ptr -> i64
%413 = arith.extsi %403 : i64 to i128
%415 = llvm.load %341 : !llvm.ptr -> i64
%414 = func.call @modpow(%396, %415, %309) : (i128, i64, i128) -> i128
%402 = func.call @mulmod(%413, %414, %309) : (i128, i128, i128) -> i128
%417 = llvm.mlir.addressof @SMAX : !llvm.ptr
%418 = llvm.load %417 : !llvm.ptr -> i64
%419 = arith.constant 1 : i32
%421 = arith.extsi %419 : i32 to i64
%420 = arith.addi %418, %421 : i64
%422 = arith.muli %337, %420 : i64
%423 = llvm.load %341 : !llvm.ptr -> i64
%424 = arith.subi %arg0, %423 : i64
%425 = arith.addi %422, %424 : i64
%426 = llvm.getelementptr %arg4[%425] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%416 = llvm.load %426 : !llvm.ptr -> i128
%401 = func.call @mulmod(%402, %416, %309) : (i128, i128, i128) -> i128
%427 = llvm.load %315 : !llvm.ptr -> i128
%429 = arith.trunci %427 : i128 to i64
%430 = arith.trunci %401 : i128 to i64
%428 = arith.addi %429, %430 : i64
%431 = arith.extsi %428 : i64 to i128
llvm.store %431, %315 : i128, !llvm.ptr
%432 = llvm.load %315 : !llvm.ptr -> i128
%434 = arith.trunci %432 : i128 to i64
%435 = arith.trunci %309 : i128 to i64
%433 = arith.cmpi sge, %434, %435 : i64
cf.cond_br %433, ^bb75, ^bb76
^bb75:
%436 = llvm.load %315 : !llvm.ptr -> i128
%438 = arith.trunci %436 : i128 to i64
%439 = arith.trunci %309 : i128 to i64
%437 = arith.subi %438, %439 : i64
%440 = arith.extsi %437 : i64 to i128
llvm.store %440, %315 : i128, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
%441 = llvm.load %341 : !llvm.ptr -> i64
%442 = arith.constant 1 : i32
%444 = arith.extsi %442 : i32 to i64
%443 = arith.addi %441, %444 : i64
llvm.store %443, %341 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
cf.br ^bb65
^bb65:
%445 = arith.constant 1 : i32
%446 = arith.trunci %445 : i32 to i8
%447 = llvm.getelementptr %arg8[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %446, %447 : i8, !llvm.ptr
%448 = llvm.getelementptr %arg6[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %300, %448 : i64, !llvm.ptr
%449 = llvm.load %315 : !llvm.ptr -> i128
%450 = llvm.getelementptr %arg7[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %449, %450 : i128, !llvm.ptr
%451 = llvm.load %315 : !llvm.ptr -> i128
func.return %451 : i128
}
func.func @get_cm(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr) -> i128 {
%452 = arith.constant 100 : i32
%454 = arith.extsi %452 : i32 to i64
%453 = arith.muli %arg0, %454 : i64
%455 = arith.addi %453, %arg1 : i64
%456 = func.call @hslot(%455, %arg2, %arg4) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%458 = llvm.getelementptr %arg4[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%457 = llvm.load %458 : !llvm.ptr -> i8
%459 = arith.constant 1 : i32
%461 = arith.extsi %457 : i8 to i32
%460 = arith.cmpi eq, %461, %459 : i32
cf.cond_br %460, ^bb78, ^bb79
^bb78:
%463 = llvm.getelementptr %arg3[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%462 = llvm.load %463 : !llvm.ptr -> i128
func.return %462 : i128
^bb79:
cf.br ^bb80
^bb80:
%465 = llvm.mlir.addressof @P : !llvm.ptr
%466 = llvm.load %465 : !llvm.ptr -> i64
%464 = func.call @ipow_mod(%466, %arg0) : (i64, i64) -> i128
%467 = arith.constant 0 : i32
%468 = arith.extsi %467 : i32 to i128
%469 = llvm.mlir.constant(1 : i64) : i64
%470 = llvm.alloca %469 x i128 : (i64) -> !llvm.ptr
llvm.store %468, %470 : i128, !llvm.ptr
%471 = arith.constant 1 : 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 ^bb81
^bb81:
%475 = llvm.load %474 : !llvm.ptr -> i64
%476 = llvm.mlir.addressof @P : !llvm.ptr
%477 = llvm.load %476 : !llvm.ptr -> i64
%478 = arith.cmpi slt, %475, %477 : i64
cf.cond_br %478, ^bb82, ^bb83
^bb82:
%480 = llvm.load %474 : !llvm.ptr -> i64
%481 = arith.extsi %480 : i64 to i128
%479 = func.call @inv_mod(%481, %464) : (i128, i128) -> i128
%482 = llvm.load %470 : !llvm.ptr -> i128
%484 = arith.constant 1 : i32
%486 = arith.extsi %484 : i32 to i64
%485 = arith.addi %arg1, %486 : i64
%483 = func.call @modpow(%479, %485, %464) : (i128, i64, i128) -> i128
%488 = arith.trunci %482 : i128 to i64
%489 = arith.trunci %483 : i128 to i64
%487 = arith.addi %488, %489 : i64
%490 = arith.extsi %487 : i64 to i128
llvm.store %490, %470 : i128, !llvm.ptr
%491 = llvm.load %470 : !llvm.ptr -> i128
%493 = arith.trunci %491 : i128 to i64
%494 = arith.trunci %464 : i128 to i64
%492 = arith.cmpi sge, %493, %494 : i64
cf.cond_br %492, ^bb84, ^bb85
^bb84:
%495 = llvm.load %470 : !llvm.ptr -> i128
%497 = arith.trunci %495 : i128 to i64
%498 = arith.trunci %464 : i128 to i64
%496 = arith.subi %497, %498 : i64
%499 = arith.extsi %496 : i64 to i128
llvm.store %499, %470 : i128, !llvm.ptr
cf.br ^bb86
^bb85:
cf.br ^bb86
^bb86:
%500 = llvm.load %474 : !llvm.ptr -> i64
%501 = arith.constant 1 : i32
%503 = arith.extsi %501 : i32 to i64
%502 = arith.addi %500, %503 : i64
llvm.store %502, %474 : i64, !llvm.ptr
cf.br ^bb81
^bb83:
%504 = arith.constant 1 : i32
%505 = arith.trunci %504 : i32 to i8
%506 = llvm.getelementptr %arg4[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %505, %506 : i8, !llvm.ptr
%507 = llvm.getelementptr %arg2[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %455, %507 : i64, !llvm.ptr
%508 = llvm.load %470 : !llvm.ptr -> i128
%509 = llvm.getelementptr %arg3[%456] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %508, %509 : i128, !llvm.ptr
%510 = llvm.load %470 : !llvm.ptr -> i128
func.return %510 : i128
}
func.func @unit_inverse_sum(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: !llvm.ptr, %arg10: !llvm.ptr, %arg11: !llvm.ptr, %arg12: !llvm.ptr, %arg13: !llvm.ptr) -> i128 {
%511 = arith.constant 0 : i32
%513 = arith.extsi %511 : i32 to i64
%512 = arith.cmpi sle, %arg0, %513 : i64
cf.cond_br %512, ^bb87, ^bb88
^bb87:
%514 = arith.constant 0 : i32
%515 = arith.extsi %514 : i32 to i128
func.return %515 : i128
^bb88:
cf.br ^bb89
^bb89:
%516 = arith.constant 20 : i32
%518 = arith.extsi %516 : i32 to i64
%517 = arith.muli %arg0, %518 : i64
%519 = arith.addi %517, %arg1 : i64
%521 = llvm.mlir.addressof @CAP : !llvm.ptr
%522 = llvm.load %521 : !llvm.ptr -> i64
%523 = arith.remsi %519, %522 : i64
%520 = func.call @hslot(%523, %arg11, %arg13) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%525 = llvm.getelementptr %arg13[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%524 = llvm.load %525 : !llvm.ptr -> i8
%526 = arith.constant 1 : i32
%528 = arith.extsi %524 : i8 to i32
%527 = arith.cmpi eq, %528, %526 : i32
%529 = scf.if %527 -> (i1) {
%531 = llvm.getelementptr %arg11[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%530 = llvm.load %531 : !llvm.ptr -> i64
%532 = arith.cmpi eq, %530, %519 : i64
scf.yield %532 : i1
} else {
%533 = arith.constant false
scf.yield %533 : i1
}
cf.cond_br %529, ^bb90, ^bb91
^bb90:
%535 = llvm.getelementptr %arg12[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%534 = llvm.load %535 : !llvm.ptr -> i128
func.return %534 : i128
^bb91:
cf.br ^bb92
^bb92:
%537 = llvm.mlir.addressof @P : !llvm.ptr
%538 = llvm.load %537 : !llvm.ptr -> i64
%536 = func.call @ipow_mod(%538, %arg1) : (i64, i64) -> i128
%539 = llvm.mlir.addressof @P : !llvm.ptr
%540 = llvm.load %539 : !llvm.ptr -> i64
%541 = arith.divsi %arg0, %540 : i64
%542 = llvm.mlir.addressof @P : !llvm.ptr
%543 = llvm.load %542 : !llvm.ptr -> i64
%544 = arith.remsi %arg0, %543 : i64
%545 = arith.constant 0 : i32
%546 = arith.extsi %545 : i32 to i128
%547 = llvm.mlir.constant(1 : i64) : i64
%548 = llvm.alloca %547 x i128 : (i64) -> !llvm.ptr
llvm.store %546, %548 : i128, !llvm.ptr
%549 = arith.constant 0 : i32
%551 = arith.extsi %549 : i32 to i64
%550 = arith.cmpi sgt, %541, %551 : i64
cf.cond_br %550, ^bb93, ^bb94
^bb93:
%552 = arith.constant 0 : i32
%553 = arith.extsi %552 : i32 to i64
%554 = llvm.mlir.constant(1 : i64) : i64
%555 = llvm.alloca %554 x i64 : (i64) -> !llvm.ptr
llvm.store %553, %555 : i64, !llvm.ptr
cf.br ^bb96
^bb96:
%556 = llvm.load %555 : !llvm.ptr -> i64
%557 = arith.cmpi slt, %556, %arg1 : i64
cf.cond_br %557, ^bb97, ^bb98
^bb97:
%559 = llvm.load %555 : !llvm.ptr -> i64
%558 = func.call @pow_sum(%559, %541, %arg1, %arg2, %arg3, %arg4, %arg5, %arg6, %arg7) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i128
%562 = llvm.mlir.addressof @P : !llvm.ptr
%563 = llvm.load %562 : !llvm.ptr -> i64
%564 = arith.extsi %563 : i64 to i128
%565 = llvm.load %555 : !llvm.ptr -> i64
%561 = func.call @modpow(%564, %565, %536) : (i128, i64, i128) -> i128
%560 = func.call @mulmod(%561, %558, %536) : (i128, i128, i128) -> i128
%566 = llvm.mlir.constant(1 : i64) : i64
%567 = llvm.alloca %566 x i128 : (i64) -> !llvm.ptr
llvm.store %560, %567 : i128, !llvm.ptr
%569 = llvm.load %567 : !llvm.ptr -> i128
%571 = llvm.load %555 : !llvm.ptr -> i64
%570 = func.call @get_cm(%arg1, %571, %arg8, %arg9, %arg10) : (i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i128
%568 = func.call @mulmod(%569, %570, %536) : (i128, i128, i128) -> i128
llvm.store %568, %567 : i128, !llvm.ptr
%572 = llvm.load %555 : !llvm.ptr -> i64
%573 = arith.constant 1 : i32
%575 = arith.extsi %573 : i32 to i64
%574 = arith.andi %572, %575 : i64
%576 = arith.constant 0 : i32
%578 = arith.extsi %576 : i32 to i64
%577 = arith.cmpi ne, %574, %578 : i64
cf.cond_br %577, ^bb99, ^bb100
^bb99:
%579 = llvm.load %567 : !llvm.ptr -> i128
%581 = arith.trunci %536 : i128 to i64
%582 = arith.trunci %579 : i128 to i64
%580 = arith.subi %581, %582 : i64
%583 = arith.extsi %580 : i64 to i128
llvm.store %583, %567 : i128, !llvm.ptr
%584 = llvm.load %567 : !llvm.ptr -> i128
%586 = arith.trunci %584 : i128 to i64
%587 = arith.trunci %536 : i128 to i64
%585 = arith.cmpi sge, %586, %587 : i64
cf.cond_br %585, ^bb102, ^bb103
^bb102:
%588 = arith.constant 0 : i32
%589 = arith.extsi %588 : i32 to i128
llvm.store %589, %567 : i128, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
%590 = llvm.load %548 : !llvm.ptr -> i128
%591 = llvm.load %567 : !llvm.ptr -> i128
%593 = arith.trunci %590 : i128 to i64
%594 = arith.trunci %591 : i128 to i64
%592 = arith.addi %593, %594 : i64
%595 = arith.extsi %592 : i64 to i128
llvm.store %595, %548 : i128, !llvm.ptr
%596 = llvm.load %548 : !llvm.ptr -> i128
%598 = arith.trunci %596 : i128 to i64
%599 = arith.trunci %536 : i128 to i64
%597 = arith.cmpi sge, %598, %599 : i64
cf.cond_br %597, ^bb105, ^bb106
^bb105:
%600 = llvm.load %548 : !llvm.ptr -> i128
%602 = arith.trunci %600 : i128 to i64
%603 = arith.trunci %536 : i128 to i64
%601 = arith.subi %602, %603 : i64
%604 = arith.extsi %601 : i64 to i128
llvm.store %604, %548 : i128, !llvm.ptr
cf.br ^bb107
^bb106:
cf.br ^bb107
^bb107:
%605 = llvm.load %555 : !llvm.ptr -> i64
%606 = arith.constant 1 : i32
%608 = arith.extsi %606 : i32 to i64
%607 = arith.addi %605, %608 : i64
llvm.store %607, %555 : i64, !llvm.ptr
cf.br ^bb96
^bb98:
cf.br ^bb95
^bb94:
cf.br ^bb95
^bb95:
%609 = llvm.mlir.addressof @P : !llvm.ptr
%610 = llvm.load %609 : !llvm.ptr -> i64
%611 = arith.muli %541, %610 : i64
%612 = arith.constant 1 : i32
%613 = arith.extsi %612 : i32 to i64
%614 = llvm.mlir.constant(1 : i64) : i64
%615 = llvm.alloca %614 x i64 : (i64) -> !llvm.ptr
llvm.store %613, %615 : i64, !llvm.ptr
cf.br ^bb108
^bb108:
%616 = llvm.load %615 : !llvm.ptr -> i64
%617 = arith.cmpi sle, %616, %544 : i64
cf.cond_br %617, ^bb109, ^bb110
^bb109:
%618 = llvm.load %615 : !llvm.ptr -> i64
%619 = llvm.mlir.addressof @P : !llvm.ptr
%620 = llvm.load %619 : !llvm.ptr -> i64
%621 = arith.remsi %618, %620 : i64
%622 = arith.constant 0 : i32
%624 = arith.extsi %622 : i32 to i64
%623 = arith.cmpi ne, %621, %624 : i64
cf.cond_br %623, ^bb111, ^bb112
^bb111:
%625 = llvm.load %548 : !llvm.ptr -> i128
%627 = llvm.load %615 : !llvm.ptr -> i64
%628 = arith.addi %611, %627 : i64
%629 = arith.extsi %628 : i64 to i128
%626 = func.call @inv_mod(%629, %536) : (i128, i128) -> i128
%631 = arith.trunci %625 : i128 to i64
%632 = arith.trunci %626 : i128 to i64
%630 = arith.addi %631, %632 : i64
%633 = arith.extsi %630 : i64 to i128
llvm.store %633, %548 : i128, !llvm.ptr
%634 = llvm.load %548 : !llvm.ptr -> i128
%636 = arith.trunci %634 : i128 to i64
%637 = arith.trunci %536 : i128 to i64
%635 = arith.cmpi sge, %636, %637 : i64
cf.cond_br %635, ^bb114, ^bb115
^bb114:
%638 = llvm.load %548 : !llvm.ptr -> i128
%640 = arith.trunci %638 : i128 to i64
%641 = arith.trunci %536 : i128 to i64
%639 = arith.subi %640, %641 : i64
%642 = arith.extsi %639 : i64 to i128
llvm.store %642, %548 : i128, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%643 = llvm.load %615 : !llvm.ptr -> i64
%644 = arith.constant 1 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.addi %643, %646 : i64
llvm.store %645, %615 : i64, !llvm.ptr
cf.br ^bb108
^bb110:
%647 = arith.constant 1 : i32
%648 = arith.trunci %647 : i32 to i8
%649 = llvm.getelementptr %arg13[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %648, %649 : i8, !llvm.ptr
%650 = llvm.getelementptr %arg11[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %519, %650 : i64, !llvm.ptr
%651 = llvm.load %548 : !llvm.ptr -> i128
%652 = llvm.getelementptr %arg12[%520] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %651, %652 : i128, !llvm.ptr
%653 = llvm.load %548 : !llvm.ptr -> i128
func.return %653 : i128
}
func.func @V_val(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: !llvm.ptr, %arg6: !llvm.ptr, %arg7: !llvm.ptr, %arg8: !llvm.ptr, %arg9: !llvm.ptr, %arg10: !llvm.ptr, %arg11: !llvm.ptr, %arg12: !llvm.ptr, %arg13: !llvm.ptr, %arg14: !llvm.ptr, %arg15: !llvm.ptr, %arg16: !llvm.ptr, %arg17: !llvm.ptr) -> i128 {
%654 = arith.constant 999995705032704 : i32
%656 = arith.extsi %654 : i32 to i64
%655 = arith.muli %arg0, %656 : i64
%657 = arith.constant 1000 : i32
%659 = arith.extsi %657 : i32 to i64
%658 = arith.muli %arg1, %659 : i64
%660 = arith.addi %655, %658 : i64
%661 = arith.addi %660, %arg2 : i64
%663 = llvm.mlir.addressof @CAP : !llvm.ptr
%664 = llvm.load %663 : !llvm.ptr -> i64
%665 = arith.remsi %661, %664 : i64
%662 = func.call @hslot(%665, %arg15, %arg17) : (i64, !llvm.ptr, !llvm.ptr) -> i64
%667 = llvm.getelementptr %arg17[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%666 = llvm.load %667 : !llvm.ptr -> i8
%668 = arith.constant 1 : i32
%670 = arith.extsi %666 : i8 to i32
%669 = arith.cmpi eq, %670, %668 : i32
%671 = scf.if %669 -> (i1) {
%673 = llvm.getelementptr %arg15[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%672 = llvm.load %673 : !llvm.ptr -> i64
%674 = arith.cmpi eq, %672, %661 : i64
scf.yield %674 : i1
} else {
%675 = arith.constant false
scf.yield %675 : i1
}
cf.cond_br %671, ^bb117, ^bb118
^bb117:
%677 = llvm.getelementptr %arg16[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%676 = llvm.load %677 : !llvm.ptr -> i128
func.return %676 : i128
^bb118:
cf.br ^bb119
^bb119:
%679 = llvm.mlir.addressof @P : !llvm.ptr
%680 = llvm.load %679 : !llvm.ptr -> i64
%678 = func.call @ipow_mod(%680, %arg2) : (i64, i64) -> i128
%681 = arith.constant 0 : i32
%682 = arith.extsi %681 : i32 to i128
%683 = llvm.mlir.constant(1 : i64) : i64
%684 = llvm.alloca %683 x i128 : (i64) -> !llvm.ptr
llvm.store %682, %684 : i128, !llvm.ptr
%685 = arith.constant 1 : i32
%686 = arith.extsi %685 : i32 to i128
%687 = llvm.mlir.constant(1 : i64) : i64
%688 = llvm.alloca %687 x i128 : (i64) -> !llvm.ptr
llvm.store %686, %688 : i128, !llvm.ptr
%689 = arith.constant 1 : i32
%690 = arith.extsi %689 : i32 to i64
%691 = llvm.mlir.constant(1 : i64) : i64
%692 = llvm.alloca %691 x i64 : (i64) -> !llvm.ptr
llvm.store %690, %692 : i64, !llvm.ptr
cf.br ^bb120
^bb120:
%693 = llvm.load %692 : !llvm.ptr -> i64
%694 = arith.cmpi sle, %693, %arg0 : i64
cf.cond_br %694, ^bb121, ^bb122
^bb121:
%696 = llvm.mlir.addressof @P : !llvm.ptr
%697 = llvm.load %696 : !llvm.ptr -> i64
%698 = llvm.load %692 : !llvm.ptr -> i64
%699 = arith.subi %arg0, %698 : i64
%695 = func.call @ipow_mod(%697, %699) : (i64, i64) -> i128
%700 = arith.extsi %arg1 : i64 to i128
%701 = llvm.load %688 : !llvm.ptr -> i128
%703 = arith.trunci %700 : i128 to i64
%704 = arith.trunci %701 : i128 to i64
%702 = arith.divsi %703, %704 : i64
%705 = llvm.load %684 : !llvm.ptr -> i128
%707 = func.call @unit_inverse_sum(%702, %arg2, %arg3, %arg4, %arg5, %arg6, %arg7, %arg8, %arg9, %arg10, %arg11, %arg12, %arg13, %arg14) : (i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i128
%706 = func.call @mulmod(%695, %707, %678) : (i128, i128, i128) -> i128
%709 = arith.trunci %705 : i128 to i64
%710 = arith.trunci %706 : i128 to i64
%708 = arith.addi %709, %710 : i64
%711 = arith.extsi %708 : i64 to i128
llvm.store %711, %684 : i128, !llvm.ptr
%712 = llvm.load %684 : !llvm.ptr -> i128
%714 = arith.trunci %712 : i128 to i64
%715 = arith.trunci %678 : i128 to i64
%713 = arith.cmpi sge, %714, %715 : i64
cf.cond_br %713, ^bb123, ^bb124
^bb123:
%716 = llvm.load %684 : !llvm.ptr -> i128
%718 = arith.trunci %716 : i128 to i64
%719 = arith.trunci %678 : i128 to i64
%717 = arith.subi %718, %719 : i64
%720 = arith.extsi %717 : i64 to i128
llvm.store %720, %684 : i128, !llvm.ptr
cf.br ^bb125
^bb124:
cf.br ^bb125
^bb125:
%721 = llvm.load %688 : !llvm.ptr -> i128
%722 = llvm.mlir.addressof @P : !llvm.ptr
%723 = llvm.load %722 : !llvm.ptr -> i64
%724 = arith.extsi %723 : i64 to i128
%726 = arith.trunci %721 : i128 to i64
%727 = arith.trunci %724 : i128 to i64
%725 = arith.muli %726, %727 : i64
%728 = arith.extsi %725 : i64 to i128
llvm.store %728, %688 : i128, !llvm.ptr
%729 = llvm.load %692 : !llvm.ptr -> i64
%730 = arith.constant 1 : i32
%732 = arith.extsi %730 : i32 to i64
%731 = arith.addi %729, %732 : i64
llvm.store %731, %692 : i64, !llvm.ptr
cf.br ^bb120
^bb122:
%733 = arith.constant 1 : i32
%734 = arith.trunci %733 : i32 to i8
%735 = llvm.getelementptr %arg17[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %734, %735 : i8, !llvm.ptr
%736 = llvm.getelementptr %arg15[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %661, %736 : i64, !llvm.ptr
%737 = llvm.load %684 : !llvm.ptr -> i128
%738 = llvm.getelementptr %arg16[%662] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %737, %738 : i128, !llvm.ptr
%739 = llvm.load %684 : !llvm.ptr -> i128
func.return %739 : i128
}
func.func @main() -> i32 {
%741 = llvm.mlir.addressof @SMAX : !llvm.ptr
%742 = llvm.load %741 : !llvm.ptr -> i64
%743 = arith.constant 1 : i32
%745 = arith.extsi %743 : i32 to i64
%744 = arith.addi %742, %745 : i64
%746 = llvm.mlir.addressof @SMAX : !llvm.ptr
%747 = llvm.load %746 : !llvm.ptr -> i64
%748 = arith.constant 1 : i32
%750 = arith.extsi %748 : i32 to i64
%749 = arith.addi %747, %750 : i64
%751 = arith.muli %744, %749 : i64
%752 = arith.constant 8 : i32
%753 = arith.extsi %752 : i32 to i64
%740 = func.call @calloc(%751, %753) : (i64, i64) -> !llvm.ptr
%755 = llvm.mlir.addressof @P : !llvm.ptr
%756 = llvm.load %755 : !llvm.ptr -> i64
%757 = arith.constant 1 : i32
%759 = arith.extsi %757 : i32 to i64
%758 = arith.addi %756, %759 : i64
%760 = llvm.mlir.addressof @SMAX : !llvm.ptr
%761 = llvm.load %760 : !llvm.ptr -> i64
%762 = arith.constant 1 : i32
%764 = arith.extsi %762 : i32 to i64
%763 = arith.addi %761, %764 : i64
%765 = arith.muli %758, %763 : i64
%766 = arith.constant 16 : i32
%767 = arith.extsi %766 : i32 to i64
%754 = func.call @calloc(%765, %767) : (i64, i64) -> !llvm.ptr
%769 = llvm.mlir.addressof @SMAX : !llvm.ptr
%770 = llvm.load %769 : !llvm.ptr -> i64
%771 = arith.constant 1 : i32
%773 = arith.extsi %771 : i32 to i64
%772 = arith.addi %770, %773 : i64
%774 = arith.constant 16 : i32
%775 = arith.extsi %774 : i32 to i64
%768 = func.call @calloc(%772, %775) : (i64, i64) -> !llvm.ptr
%777 = llvm.mlir.addressof @P : !llvm.ptr
%778 = llvm.load %777 : !llvm.ptr -> i64
%779 = arith.constant 8 : i32
%780 = arith.extsi %779 : i32 to i64
%776 = func.call @calloc(%778, %780) : (i64, i64) -> !llvm.ptr
%782 = llvm.mlir.addressof @P : !llvm.ptr
%783 = llvm.load %782 : !llvm.ptr -> i64
%784 = llvm.mlir.addressof @P : !llvm.ptr
%785 = llvm.load %784 : !llvm.ptr -> i64
%786 = arith.muli %783, %785 : i64
%787 = arith.constant 8 : i32
%788 = arith.extsi %787 : i32 to i64
%781 = func.call @calloc(%786, %788) : (i64, i64) -> !llvm.ptr
%789 = llvm.mlir.zero : !llvm.ptr
%790 = llvm.icmp "eq" %740, %789 : !llvm.ptr
%791 = scf.if %790 -> (i1) {
%792 = arith.constant true
scf.yield %792 : i1
} else {
%793 = llvm.mlir.zero : !llvm.ptr
%794 = llvm.icmp "eq" %754, %793 : !llvm.ptr
scf.yield %794 : i1
}
%795 = scf.if %791 -> (i1) {
%796 = arith.constant true
scf.yield %796 : i1
} else {
%797 = llvm.mlir.zero : !llvm.ptr
%798 = llvm.icmp "eq" %768, %797 : !llvm.ptr
scf.yield %798 : i1
}
%799 = scf.if %795 -> (i1) {
%800 = arith.constant true
scf.yield %800 : i1
} else {
%801 = llvm.mlir.zero : !llvm.ptr
%802 = llvm.icmp "eq" %776, %801 : !llvm.ptr
scf.yield %802 : i1
}
%803 = scf.if %799 -> (i1) {
%804 = arith.constant true
scf.yield %804 : i1
} else {
%805 = llvm.mlir.zero : !llvm.ptr
%806 = llvm.icmp "eq" %781, %805 : !llvm.ptr
scf.yield %806 : i1
}
cf.cond_br %803, ^bb126, ^bb127
^bb126:
%807 = arith.constant 1 : i32
func.return %807 : i32
^bb127:
cf.br ^bb128
^bb128:
%808 = arith.constant 0 : i32
%809 = arith.extsi %808 : i32 to i64
%810 = llvm.mlir.constant(1 : i64) : i64
%811 = llvm.alloca %810 x i64 : (i64) -> !llvm.ptr
llvm.store %809, %811 : i64, !llvm.ptr
cf.br ^bb129
^bb129:
%812 = llvm.load %811 : !llvm.ptr -> i64
%813 = llvm.mlir.addressof @SMAX : !llvm.ptr
%814 = llvm.load %813 : !llvm.ptr -> i64
%815 = arith.cmpi sle, %812, %814 : i64
cf.cond_br %815, ^bb130, ^bb131
^bb130:
%816 = arith.constant 1 : i32
%817 = llvm.load %811 : !llvm.ptr -> i64
%818 = llvm.mlir.addressof @SMAX : !llvm.ptr
%819 = llvm.load %818 : !llvm.ptr -> i64
%820 = arith.constant 1 : i32
%822 = arith.extsi %820 : i32 to i64
%821 = arith.addi %819, %822 : i64
%823 = arith.muli %817, %821 : i64
%824 = arith.constant 0 : i32
%826 = arith.extsi %824 : i32 to i64
%825 = arith.addi %823, %826 : i64
%827 = arith.extsi %816 : i32 to i64
%828 = llvm.getelementptr %740[%825] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %827, %828 : i64, !llvm.ptr
%829 = arith.constant 1 : i32
%830 = llvm.load %811 : !llvm.ptr -> i64
%831 = llvm.mlir.addressof @SMAX : !llvm.ptr
%832 = llvm.load %831 : !llvm.ptr -> i64
%833 = arith.constant 1 : i32
%835 = arith.extsi %833 : i32 to i64
%834 = arith.addi %832, %835 : i64
%836 = arith.muli %830, %834 : i64
%837 = llvm.load %811 : !llvm.ptr -> i64
%838 = arith.addi %836, %837 : i64
%839 = arith.extsi %829 : i32 to i64
%840 = llvm.getelementptr %740[%838] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %839, %840 : i64, !llvm.ptr
%841 = arith.constant 1 : i32
%842 = arith.extsi %841 : i32 to i64
%843 = llvm.mlir.constant(1 : i64) : i64
%844 = llvm.alloca %843 x i64 : (i64) -> !llvm.ptr
llvm.store %842, %844 : i64, !llvm.ptr
cf.br ^bb132
^bb132:
%845 = llvm.load %844 : !llvm.ptr -> i64
%846 = llvm.load %811 : !llvm.ptr -> i64
%847 = arith.cmpi slt, %845, %846 : i64
cf.cond_br %847, ^bb133, ^bb134
^bb133:
%849 = llvm.load %811 : !llvm.ptr -> i64
%850 = arith.constant 1 : i32
%852 = arith.extsi %850 : i32 to i64
%851 = arith.subi %849, %852 : i64
%853 = llvm.mlir.addressof @SMAX : !llvm.ptr
%854 = llvm.load %853 : !llvm.ptr -> i64
%855 = arith.constant 1 : i32
%857 = arith.extsi %855 : i32 to i64
%856 = arith.addi %854, %857 : i64
%858 = arith.muli %851, %856 : i64
%859 = llvm.load %844 : !llvm.ptr -> i64
%860 = arith.constant 1 : i32
%862 = arith.extsi %860 : i32 to i64
%861 = arith.subi %859, %862 : i64
%863 = arith.addi %858, %861 : i64
%864 = llvm.getelementptr %740[%863] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%848 = llvm.load %864 : !llvm.ptr -> i64
%866 = llvm.load %811 : !llvm.ptr -> i64
%867 = arith.constant 1 : i32
%869 = arith.extsi %867 : i32 to i64
%868 = arith.subi %866, %869 : i64
%870 = llvm.mlir.addressof @SMAX : !llvm.ptr
%871 = llvm.load %870 : !llvm.ptr -> i64
%872 = arith.constant 1 : i32
%874 = arith.extsi %872 : i32 to i64
%873 = arith.addi %871, %874 : i64
%875 = arith.muli %868, %873 : i64
%876 = llvm.load %844 : !llvm.ptr -> i64
%877 = arith.addi %875, %876 : i64
%878 = llvm.getelementptr %740[%877] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%865 = llvm.load %878 : !llvm.ptr -> i64
%879 = arith.addi %848, %865 : i64
%880 = llvm.load %811 : !llvm.ptr -> i64
%881 = llvm.mlir.addressof @SMAX : !llvm.ptr
%882 = llvm.load %881 : !llvm.ptr -> i64
%883 = arith.constant 1 : i32
%885 = arith.extsi %883 : i32 to i64
%884 = arith.addi %882, %885 : i64
%886 = arith.muli %880, %884 : i64
%887 = llvm.load %844 : !llvm.ptr -> i64
%888 = arith.addi %886, %887 : i64
%889 = llvm.getelementptr %740[%888] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %879, %889 : i64, !llvm.ptr
%890 = llvm.load %844 : !llvm.ptr -> i64
%891 = arith.constant 1 : i32
%893 = arith.extsi %891 : i32 to i64
%892 = arith.addi %890, %893 : i64
llvm.store %892, %844 : i64, !llvm.ptr
cf.br ^bb132
^bb134:
%894 = llvm.load %811 : !llvm.ptr -> i64
%895 = arith.constant 1 : i32
%897 = arith.extsi %895 : i32 to i64
%896 = arith.addi %894, %897 : i64
llvm.store %896, %811 : i64, !llvm.ptr
cf.br ^bb129
^bb131:
%898 = arith.constant 1 : i32
%899 = arith.extsi %898 : i32 to i64
%900 = llvm.mlir.constant(1 : i64) : i64
%901 = llvm.alloca %900 x i64 : (i64) -> !llvm.ptr
llvm.store %899, %901 : i64, !llvm.ptr
cf.br ^bb135
^bb135:
%902 = llvm.load %901 : !llvm.ptr -> i64
%903 = llvm.mlir.addressof @P : !llvm.ptr
%904 = llvm.load %903 : !llvm.ptr -> i64
%905 = arith.cmpi sle, %902, %904 : i64
cf.cond_br %905, ^bb136, ^bb137
^bb136:
%906 = llvm.load %901 : !llvm.ptr -> i64
%907 = arith.constant 1 : i32
%909 = arith.extsi %907 : i32 to i64
%908 = arith.subi %906, %909 : i64
%910 = arith.constant 0 : i32
%911 = arith.extsi %910 : i32 to i64
%912 = llvm.mlir.constant(1 : i64) : i64
%913 = llvm.alloca %912 x i64 : (i64) -> !llvm.ptr
llvm.store %911, %913 : i64, !llvm.ptr
cf.br ^bb138
^bb138:
%914 = llvm.load %913 : !llvm.ptr -> i64
%915 = llvm.mlir.addressof @SMAX : !llvm.ptr
%916 = llvm.load %915 : !llvm.ptr -> i64
%917 = arith.cmpi sle, %914, %916 : i64
cf.cond_br %917, ^bb139, ^bb140
^bb139:
%919 = llvm.load %901 : !llvm.ptr -> i64
%920 = arith.constant 1 : i32
%922 = arith.extsi %920 : i32 to i64
%921 = arith.subi %919, %922 : i64
%923 = llvm.mlir.addressof @SMAX : !llvm.ptr
%924 = llvm.load %923 : !llvm.ptr -> i64
%925 = arith.constant 1 : i32
%927 = arith.extsi %925 : i32 to i64
%926 = arith.addi %924, %927 : i64
%928 = arith.muli %921, %926 : i64
%929 = llvm.load %913 : !llvm.ptr -> i64
%930 = arith.addi %928, %929 : i64
%931 = llvm.getelementptr %754[%930] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%918 = llvm.load %931 : !llvm.ptr -> i128
%933 = llvm.load %913 : !llvm.ptr -> i64
%932 = func.call @ipow_mod(%908, %933) : (i64, i64) -> i128
%935 = arith.trunci %918 : i128 to i64
%936 = arith.trunci %932 : i128 to i64
%934 = arith.addi %935, %936 : i64
%937 = llvm.load %901 : !llvm.ptr -> i64
%938 = llvm.mlir.addressof @SMAX : !llvm.ptr
%939 = llvm.load %938 : !llvm.ptr -> i64
%940 = arith.constant 1 : i32
%942 = arith.extsi %940 : i32 to i64
%941 = arith.addi %939, %942 : i64
%943 = arith.muli %937, %941 : i64
%944 = llvm.load %913 : !llvm.ptr -> i64
%945 = arith.addi %943, %944 : i64
%946 = arith.extsi %934 : i64 to i128
%947 = llvm.getelementptr %754[%945] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %946, %947 : i128, !llvm.ptr
%948 = llvm.load %913 : !llvm.ptr -> i64
%949 = arith.constant 1 : i32
%951 = arith.extsi %949 : i32 to i64
%950 = arith.addi %948, %951 : i64
llvm.store %950, %913 : i64, !llvm.ptr
cf.br ^bb138
^bb140:
%952 = llvm.load %901 : !llvm.ptr -> i64
%953 = arith.constant 1 : i32
%955 = arith.extsi %953 : i32 to i64
%954 = arith.addi %952, %955 : i64
llvm.store %954, %901 : i64, !llvm.ptr
cf.br ^bb135
^bb137:
%956 = arith.constant 0 : i32
%957 = arith.extsi %956 : i32 to i64
%958 = llvm.mlir.constant(1 : i64) : i64
%959 = llvm.alloca %958 x i64 : (i64) -> !llvm.ptr
llvm.store %957, %959 : i64, !llvm.ptr
cf.br ^bb141
^bb141:
%960 = llvm.load %959 : !llvm.ptr -> i64
%961 = llvm.mlir.addressof @SMAX : !llvm.ptr
%962 = llvm.load %961 : !llvm.ptr -> i64
%963 = arith.cmpi sle, %960, %962 : i64
cf.cond_br %963, ^bb142, ^bb143
^bb142:
%965 = llvm.mlir.addressof @P : !llvm.ptr
%966 = llvm.load %965 : !llvm.ptr -> i64
%967 = llvm.mlir.addressof @SMAX : !llvm.ptr
%968 = llvm.load %967 : !llvm.ptr -> i64
%969 = arith.constant 1 : i32
%971 = arith.extsi %969 : i32 to i64
%970 = arith.addi %968, %971 : i64
%972 = arith.muli %966, %970 : i64
%973 = llvm.load %959 : !llvm.ptr -> i64
%974 = arith.addi %972, %973 : i64
%975 = llvm.getelementptr %754[%974] : (!llvm.ptr, i64) -> !llvm.ptr, i128
%964 = llvm.load %975 : !llvm.ptr -> i128
%976 = llvm.load %959 : !llvm.ptr -> i64
%977 = llvm.getelementptr %768[%976] : (!llvm.ptr, i64) -> !llvm.ptr, i128
llvm.store %964, %977 : i128, !llvm.ptr
%978 = llvm.load %959 : !llvm.ptr -> i64
%979 = arith.constant 1 : i32
%981 = arith.extsi %979 : i32 to i64
%980 = arith.addi %978, %981 : i64
llvm.store %980, %959 : i64, !llvm.ptr
cf.br ^bb141
^bb143:
%983 = llvm.mlir.addressof @P : !llvm.ptr
%984 = llvm.load %983 : !llvm.ptr -> i64
%985 = arith.constant 8 : i32
%986 = arith.extsi %985 : i32 to i64
%982 = func.call @calloc(%984, %986) : (i64, i64) -> !llvm.ptr
%988 = llvm.mlir.addressof @P : !llvm.ptr
%989 = llvm.load %988 : !llvm.ptr -> i64
%990 = arith.constant 8 : i32
%991 = arith.extsi %990 : i32 to i64
%987 = func.call @calloc(%989, %991) : (i64, i64) -> !llvm.ptr
%992 = llvm.mlir.zero : !llvm.ptr
%993 = llvm.icmp "eq" %982, %992 : !llvm.ptr
%994 = scf.if %993 -> (i1) {
%995 = arith.constant true
scf.yield %995 : i1
} else {
%996 = llvm.mlir.zero : !llvm.ptr
%997 = llvm.icmp "eq" %987, %996 : !llvm.ptr
scf.yield %997 : i1
}
cf.cond_br %994, ^bb144, ^bb145
^bb144:
%998 = arith.constant 1 : i32
func.return %998 : i32
^bb145:
cf.br ^bb146
^bb146:
%999 = arith.constant 1 : i32
%1000 = arith.extsi %999 : i32 to i64
%1001 = llvm.mlir.constant(1 : i64) : i64
%1002 = llvm.alloca %1001 x i64 : (i64) -> !llvm.ptr
llvm.store %1000, %1002 : i64, !llvm.ptr
cf.br ^bb147
^bb147:
%1003 = llvm.load %1002 : !llvm.ptr -> i64
%1004 = llvm.mlir.addressof @P : !llvm.ptr
%1005 = llvm.load %1004 : !llvm.ptr -> i64
%1006 = arith.cmpi slt, %1003, %1005 : i64
cf.cond_br %1006, ^bb148, ^bb149
^bb148:
%1008 = llvm.load %1002 : !llvm.ptr -> i64
%1009 = arith.extsi %1008 : i64 to i128
%1010 = llvm.mlir.addressof @P : !llvm.ptr
%1011 = llvm.load %1010 : !llvm.ptr -> i64
%1012 = arith.extsi %1011 : i64 to i128
%1007 = func.call @inv_mod(%1009, %1012) : (i128, i128) -> i128
%1013 = arith.trunci %1007 : i128 to i64
%1014 = llvm.load %1002 : !llvm.ptr -> i64
%1015 = llvm.getelementptr %982[%1014] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1013, %1015 : i64, !llvm.ptr
%1016 = llvm.load %1002 : !llvm.ptr -> i64
%1017 = arith.constant 1 : i32
%1019 = arith.extsi %1017 : i32 to i64
%1018 = arith.addi %1016, %1019 : i64
llvm.store %1018, %1002 : i64, !llvm.ptr
cf.br ^bb147
^bb149:
%1020 = arith.constant 0 : i32
%1021 = arith.extsi %1020 : i32 to i64
%1022 = llvm.mlir.constant(1 : i64) : i64
%1023 = llvm.alloca %1022 x i64 : (i64) -> !llvm.ptr
llvm.store %1021, %1023 : i64, !llvm.ptr
%1024 = arith.constant 1 : i32
%1025 = arith.extsi %1024 : i32 to i64
llvm.store %1025, %1002 : i64, !llvm.ptr
cf.br ^bb150
^bb150:
%1026 = llvm.load %1002 : !llvm.ptr -> i64
%1027 = llvm.mlir.addressof @P : !llvm.ptr
%1028 = llvm.load %1027 : !llvm.ptr -> i64
%1029 = arith.cmpi slt, %1026, %1028 : i64
cf.cond_br %1029, ^bb151, ^bb152
^bb151:
%1030 = llvm.load %1023 : !llvm.ptr -> i64
%1032 = llvm.load %1002 : !llvm.ptr -> i64
%1033 = llvm.getelementptr %982[%1032] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1031 = llvm.load %1033 : !llvm.ptr -> i64
%1034 = arith.addi %1030, %1031 : i64
%1035 = llvm.mlir.addressof @P : !llvm.ptr
%1036 = llvm.load %1035 : !llvm.ptr -> i64
%1037 = arith.remsi %1034, %1036 : i64
llvm.store %1037, %1023 : i64, !llvm.ptr
%1038 = llvm.load %1023 : !llvm.ptr -> i64
%1039 = llvm.load %1002 : !llvm.ptr -> i64
%1040 = llvm.getelementptr %987[%1039] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1038, %1040 : i64, !llvm.ptr
%1041 = llvm.load %1002 : !llvm.ptr -> i64
%1042 = arith.constant 1 : i32
%1044 = arith.extsi %1042 : i32 to i64
%1043 = arith.addi %1041, %1044 : i64
llvm.store %1043, %1002 : i64, !llvm.ptr
cf.br ^bb150
^bb152:
%1045 = arith.constant 0 : i32
%1046 = arith.constant 0 : i32
%1047 = arith.extsi %1045 : i32 to i64
%1048 = arith.extsi %1046 : i32 to i64
%1049 = llvm.getelementptr %987[%1048] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1047, %1049 : i64, !llvm.ptr
%1050 = arith.constant 0 : i32
%1051 = arith.extsi %1050 : i32 to i64
llvm.store %1051, %1002 : i64, !llvm.ptr
cf.br ^bb153
^bb153:
%1052 = llvm.load %1002 : !llvm.ptr -> i64
%1053 = llvm.mlir.addressof @P : !llvm.ptr
%1054 = llvm.load %1053 : !llvm.ptr -> i64
%1055 = arith.cmpi slt, %1052, %1054 : i64
cf.cond_br %1055, ^bb154, ^bb155
^bb154:
%1057 = llvm.load %1002 : !llvm.ptr -> i64
%1058 = llvm.getelementptr %987[%1057] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1056 = llvm.load %1058 : !llvm.ptr -> i64
%1060 = llvm.getelementptr %776[%1056] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1059 = llvm.load %1060 : !llvm.ptr -> i64
%1061 = llvm.load %1002 : !llvm.ptr -> i64
%1062 = llvm.mlir.addressof @P : !llvm.ptr
%1063 = llvm.load %1062 : !llvm.ptr -> i64
%1064 = arith.muli %1056, %1063 : i64
%1065 = arith.addi %1064, %1059 : i64
%1066 = llvm.getelementptr %781[%1065] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1061, %1066 : i64, !llvm.ptr
%1067 = arith.constant 1 : i32
%1069 = arith.extsi %1067 : i32 to i64
%1068 = arith.addi %1059, %1069 : i64
%1070 = llvm.getelementptr %776[%1056] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1068, %1070 : i64, !llvm.ptr
%1071 = llvm.load %1002 : !llvm.ptr -> i64
%1072 = arith.constant 1 : i32
%1074 = arith.extsi %1072 : i32 to i64
%1073 = arith.addi %1071, %1074 : i64
llvm.store %1073, %1002 : i64, !llvm.ptr
cf.br ^bb153
^bb155:
%1076 = llvm.mlir.addressof @CAP : !llvm.ptr
%1077 = llvm.load %1076 : !llvm.ptr -> i64
%1078 = arith.constant 8 : i32
%1079 = arith.extsi %1078 : i32 to i64
%1075 = func.call @calloc(%1077, %1079) : (i64, i64) -> !llvm.ptr
%1081 = llvm.mlir.addressof @CAP : !llvm.ptr
%1082 = llvm.load %1081 : !llvm.ptr -> i64
%1083 = arith.constant 16 : i32
%1084 = arith.extsi %1083 : i32 to i64
%1080 = func.call @calloc(%1082, %1084) : (i64, i64) -> !llvm.ptr
%1086 = llvm.mlir.addressof @CAP : !llvm.ptr
%1087 = llvm.load %1086 : !llvm.ptr -> i64
%1088 = arith.constant 1 : i32
%1089 = arith.extsi %1088 : i32 to i64
%1085 = func.call @calloc(%1087, %1089) : (i64, i64) -> !llvm.ptr
%1091 = llvm.mlir.addressof @CAP : !llvm.ptr
%1092 = llvm.load %1091 : !llvm.ptr -> i64
%1093 = arith.constant 8 : i32
%1094 = arith.extsi %1093 : i32 to i64
%1090 = func.call @calloc(%1092, %1094) : (i64, i64) -> !llvm.ptr
%1096 = llvm.mlir.addressof @CAP : !llvm.ptr
%1097 = llvm.load %1096 : !llvm.ptr -> i64
%1098 = arith.constant 16 : i32
%1099 = arith.extsi %1098 : i32 to i64
%1095 = func.call @calloc(%1097, %1099) : (i64, i64) -> !llvm.ptr
%1101 = llvm.mlir.addressof @CAP : !llvm.ptr
%1102 = llvm.load %1101 : !llvm.ptr -> i64
%1103 = arith.constant 1 : i32
%1104 = arith.extsi %1103 : i32 to i64
%1100 = func.call @calloc(%1102, %1104) : (i64, i64) -> !llvm.ptr
%1106 = llvm.mlir.addressof @CAP : !llvm.ptr
%1107 = llvm.load %1106 : !llvm.ptr -> i64
%1108 = arith.constant 8 : i32
%1109 = arith.extsi %1108 : i32 to i64
%1105 = func.call @calloc(%1107, %1109) : (i64, i64) -> !llvm.ptr
%1111 = llvm.mlir.addressof @CAP : !llvm.ptr
%1112 = llvm.load %1111 : !llvm.ptr -> i64
%1113 = arith.constant 16 : i32
%1114 = arith.extsi %1113 : i32 to i64
%1110 = func.call @calloc(%1112, %1114) : (i64, i64) -> !llvm.ptr
%1116 = llvm.mlir.addressof @CAP : !llvm.ptr
%1117 = llvm.load %1116 : !llvm.ptr -> i64
%1118 = arith.constant 1 : i32
%1119 = arith.extsi %1118 : i32 to i64
%1115 = func.call @calloc(%1117, %1119) : (i64, i64) -> !llvm.ptr
%1121 = llvm.mlir.addressof @CAP : !llvm.ptr
%1122 = llvm.load %1121 : !llvm.ptr -> i64
%1123 = arith.constant 8 : i32
%1124 = arith.extsi %1123 : i32 to i64
%1120 = func.call @calloc(%1122, %1124) : (i64, i64) -> !llvm.ptr
%1126 = llvm.mlir.addressof @CAP : !llvm.ptr
%1127 = llvm.load %1126 : !llvm.ptr -> i64
%1128 = arith.constant 16 : i32
%1129 = arith.extsi %1128 : i32 to i64
%1125 = func.call @calloc(%1127, %1129) : (i64, i64) -> !llvm.ptr
%1131 = llvm.mlir.addressof @CAP : !llvm.ptr
%1132 = llvm.load %1131 : !llvm.ptr -> i64
%1133 = arith.constant 1 : i32
%1134 = arith.extsi %1133 : i32 to i64
%1130 = func.call @calloc(%1132, %1134) : (i64, i64) -> !llvm.ptr
%1136 = arith.constant 4096 : i32
%1137 = arith.constant 8 : i32
%1138 = arith.extsi %1136 : i32 to i64
%1139 = arith.extsi %1137 : i32 to i64
%1135 = func.call @calloc(%1138, %1139) : (i64, i64) -> !llvm.ptr
%1141 = arith.constant 1 : i32
%1142 = arith.constant 8 : i32
%1143 = arith.extsi %1141 : i32 to i64
%1144 = arith.extsi %1142 : i32 to i64
%1140 = func.call @calloc(%1143, %1144) : (i64, i64) -> !llvm.ptr
%1145 = llvm.mlir.zero : !llvm.ptr
%1146 = llvm.icmp "eq" %1075, %1145 : !llvm.ptr
%1147 = scf.if %1146 -> (i1) {
%1148 = arith.constant true
scf.yield %1148 : i1
} else {
%1149 = llvm.mlir.zero : !llvm.ptr
%1150 = llvm.icmp "eq" %1080, %1149 : !llvm.ptr
scf.yield %1150 : i1
}
%1151 = scf.if %1147 -> (i1) {
%1152 = arith.constant true
scf.yield %1152 : i1
} else {
%1153 = llvm.mlir.zero : !llvm.ptr
%1154 = llvm.icmp "eq" %1085, %1153 : !llvm.ptr
scf.yield %1154 : i1
}
cf.cond_br %1151, ^bb156, ^bb157
^bb156:
%1155 = arith.constant 1 : i32
func.return %1155 : i32
^bb157:
cf.br ^bb158
^bb158:
%1156 = llvm.mlir.addressof @P : !llvm.ptr
%1157 = llvm.load %1156 : !llvm.ptr -> i64
%1158 = arith.constant 1 : i32
%1160 = arith.extsi %1158 : i32 to i64
%1159 = arith.subi %1157, %1160 : i64
%1161 = llvm.mlir.constant(1 : i64) : i64
%1162 = llvm.alloca %1161 x i64 : (i64) -> !llvm.ptr
llvm.store %1159, %1162 : i64, !llvm.ptr
%1163 = arith.constant 0 : i32
%1164 = arith.constant 0 : i32
%1165 = arith.extsi %1163 : i32 to i64
%1166 = arith.extsi %1164 : i32 to i64
%1167 = llvm.getelementptr %1140[%1166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1165, %1167 : i64, !llvm.ptr
%1168 = arith.constant 0 : i32
%1169 = arith.extsi %1168 : i32 to i64
%1170 = llvm.mlir.constant(1 : i64) : i64
%1171 = llvm.alloca %1170 x i64 : (i64) -> !llvm.ptr
llvm.store %1169, %1171 : i64, !llvm.ptr
cf.br ^bb159
^bb159:
%1172 = llvm.load %1171 : !llvm.ptr -> i64
%1174 = arith.constant 0 : i32
%1175 = arith.extsi %1174 : i32 to i64
%1176 = llvm.getelementptr %776[%1175] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1173 = llvm.load %1176 : !llvm.ptr -> i64
%1177 = arith.cmpi slt, %1172, %1173 : i64
cf.cond_br %1177, ^bb160, ^bb161
^bb160:
%1179 = arith.constant 0 : i32
%1180 = llvm.mlir.addressof @P : !llvm.ptr
%1181 = llvm.load %1180 : !llvm.ptr -> i64
%1183 = arith.extsi %1179 : i32 to i64
%1182 = arith.muli %1183, %1181 : i64
%1184 = llvm.load %1171 : !llvm.ptr -> i64
%1185 = arith.addi %1182, %1184 : i64
%1186 = llvm.getelementptr %781[%1185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1178 = llvm.load %1186 : !llvm.ptr -> i64
%1187 = arith.constant 1 : i32
%1189 = arith.extsi %1187 : i32 to i64
%1188 = arith.cmpi sge, %1178, %1189 : i64
%1190 = scf.if %1188 -> (i1) {
%1191 = llvm.mlir.addressof @P : !llvm.ptr
%1192 = llvm.load %1191 : !llvm.ptr -> i64
%1193 = arith.cmpi slt, %1178, %1192 : i64
scf.yield %1193 : i1
} else {
%1194 = arith.constant false
scf.yield %1194 : i1
}
cf.cond_br %1190, ^bb162, ^bb163
^bb162:
%1196 = arith.constant 0 : i32
%1197 = arith.extsi %1196 : i32 to i64
%1198 = llvm.getelementptr %1140[%1197] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1195 = llvm.load %1198 : !llvm.ptr -> i64
%1199 = llvm.getelementptr %1135[%1195] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1178, %1199 : i64, !llvm.ptr
%1201 = arith.constant 0 : i32
%1202 = arith.extsi %1201 : i32 to i64
%1203 = llvm.getelementptr %1140[%1202] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1200 = llvm.load %1203 : !llvm.ptr -> i64
%1204 = arith.constant 1 : i32
%1206 = arith.extsi %1204 : i32 to i64
%1205 = arith.addi %1200, %1206 : i64
%1207 = arith.constant 0 : i32
%1208 = arith.extsi %1207 : i32 to i64
%1209 = llvm.getelementptr %1140[%1208] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1205, %1209 : i64, !llvm.ptr
cf.br ^bb164
^bb163:
cf.br ^bb164
^bb164:
%1210 = llvm.load %1171 : !llvm.ptr -> i64
%1211 = arith.constant 1 : i32
%1213 = arith.extsi %1211 : i32 to i64
%1212 = arith.addi %1210, %1213 : i64
llvm.store %1212, %1171 : i64, !llvm.ptr
cf.br ^bb159
^bb161:
%1214 = arith.constant 1 : i32
%1215 = arith.extsi %1214 : i32 to i64
%1216 = llvm.mlir.constant(1 : i64) : i64
%1217 = llvm.alloca %1216 x i64 : (i64) -> !llvm.ptr
llvm.store %1215, %1217 : i64, !llvm.ptr
cf.br ^bb165
^bb165:
%1219 = arith.constant 0 : i32
%1220 = arith.extsi %1219 : i32 to i64
%1221 = llvm.getelementptr %1140[%1220] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1218 = llvm.load %1221 : !llvm.ptr -> i64
%1222 = arith.constant 0 : i32
%1224 = arith.extsi %1222 : i32 to i64
%1223 = arith.cmpi sgt, %1218, %1224 : i64
cf.cond_br %1223, ^bb166, ^bb167
^bb166:
%1225 = arith.constant 0 : i32
%1226 = arith.extsi %1225 : i32 to i64
%1227 = llvm.mlir.constant(1 : i64) : i64
%1228 = llvm.alloca %1227 x i64 : (i64) -> !llvm.ptr
llvm.store %1226, %1228 : i64, !llvm.ptr
%1229 = arith.constant 0 : i32
%1230 = arith.extsi %1229 : i32 to i64
llvm.store %1230, %1171 : i64, !llvm.ptr
cf.br ^bb168
^bb168:
%1231 = llvm.load %1171 : !llvm.ptr -> i64
%1233 = arith.constant 0 : i32
%1234 = arith.extsi %1233 : i32 to i64
%1235 = llvm.getelementptr %1140[%1234] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1232 = llvm.load %1235 : !llvm.ptr -> i64
%1236 = arith.cmpi slt, %1231, %1232 : i64
cf.cond_br %1236, ^bb169, ^bb170
^bb169:
%1238 = llvm.load %1171 : !llvm.ptr -> i64
%1239 = llvm.getelementptr %1135[%1238] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1237 = llvm.load %1239 : !llvm.ptr -> i64
%1240 = llvm.load %1228 : !llvm.ptr -> i64
%1241 = arith.cmpi sgt, %1237, %1240 : i64
cf.cond_br %1241, ^bb171, ^bb172
^bb171:
%1243 = llvm.load %1171 : !llvm.ptr -> i64
%1244 = llvm.getelementptr %1135[%1243] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1242 = llvm.load %1244 : !llvm.ptr -> i64
llvm.store %1242, %1228 : i64, !llvm.ptr
cf.br ^bb173
^bb172:
cf.br ^bb173
^bb173:
%1245 = llvm.load %1171 : !llvm.ptr -> i64
%1246 = arith.constant 1 : i32
%1248 = arith.extsi %1246 : i32 to i64
%1247 = arith.addi %1245, %1248 : i64
llvm.store %1247, %1171 : i64, !llvm.ptr
cf.br ^bb168
^bb170:
%1249 = llvm.mlir.addressof @P : !llvm.ptr
%1250 = llvm.load %1249 : !llvm.ptr -> i64
%1251 = llvm.load %1228 : !llvm.ptr -> i64
%1252 = arith.muli %1250, %1251 : i64
%1253 = llvm.mlir.addressof @P : !llvm.ptr
%1254 = llvm.load %1253 : !llvm.ptr -> i64
%1255 = arith.constant 1 : i32
%1257 = arith.extsi %1255 : i32 to i64
%1256 = arith.subi %1254, %1257 : i64
%1258 = arith.addi %1252, %1256 : i64
llvm.store %1258, %1162 : i64, !llvm.ptr
%1260 = arith.constant 4096 : i32
%1261 = arith.constant 8 : i32
%1262 = arith.extsi %1260 : i32 to i64
%1263 = arith.extsi %1261 : i32 to i64
%1259 = func.call @calloc(%1262, %1263) : (i64, i64) -> !llvm.ptr
%1264 = arith.constant 0 : i32
%1265 = arith.extsi %1264 : i32 to i64
%1266 = llvm.mlir.constant(1 : i64) : i64
%1267 = llvm.alloca %1266 x i64 : (i64) -> !llvm.ptr
llvm.store %1265, %1267 : i64, !llvm.ptr
%1268 = arith.constant 0 : i32
%1269 = arith.extsi %1268 : i32 to i64
llvm.store %1269, %1171 : i64, !llvm.ptr
cf.br ^bb174
^bb174:
%1270 = llvm.load %1171 : !llvm.ptr -> i64
%1272 = arith.constant 0 : i32
%1273 = arith.extsi %1272 : i32 to i64
%1274 = llvm.getelementptr %1140[%1273] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1271 = llvm.load %1274 : !llvm.ptr -> i64
%1275 = arith.cmpi slt, %1270, %1271 : i64
cf.cond_br %1275, ^bb175, ^bb176
^bb175:
%1277 = llvm.load %1171 : !llvm.ptr -> i64
%1278 = llvm.getelementptr %1135[%1277] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1276 = llvm.load %1278 : !llvm.ptr -> i64
%1280 = llvm.load %1217 : !llvm.ptr -> i64
%1281 = llvm.load %1217 : !llvm.ptr -> i64
%1282 = arith.constant 1 : i32
%1284 = arith.extsi %1282 : i32 to i64
%1283 = arith.addi %1281, %1284 : i64
%1279 = func.call @V_val(%1280, %1276, %1283, %740, %754, %768, %1075, %1080, %1085, %1090, %1095, %1100, %1105, %1110, %1115, %1120, %1125, %1130) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr, !llvm.ptr) -> i128
%1286 = llvm.mlir.addressof @P : !llvm.ptr
%1287 = llvm.load %1286 : !llvm.ptr -> i64
%1288 = llvm.load %1217 : !llvm.ptr -> i64
%1285 = func.call @ipow_mod(%1287, %1288) : (i64, i64) -> i128
%1290 = arith.trunci %1279 : i128 to i64
%1291 = arith.trunci %1285 : i128 to i64
%1289 = arith.divsi %1290, %1291 : i64
%1292 = llvm.mlir.addressof @P : !llvm.ptr
%1293 = llvm.load %1292 : !llvm.ptr -> i64
%1294 = arith.extsi %1293 : i64 to i128
%1296 = arith.trunci %1294 : i128 to i64
%1295 = arith.remsi %1289, %1296 : i64
%1297 = llvm.mlir.addressof @P : !llvm.ptr
%1298 = llvm.load %1297 : !llvm.ptr -> i64
%1299 = arith.subi %1298, %1295 : i64
%1300 = llvm.mlir.addressof @P : !llvm.ptr
%1301 = llvm.load %1300 : !llvm.ptr -> i64
%1302 = arith.remsi %1299, %1301 : i64
%1303 = arith.constant 0 : i32
%1304 = arith.extsi %1303 : i32 to i64
%1305 = llvm.mlir.constant(1 : i64) : i64
%1306 = llvm.alloca %1305 x i64 : (i64) -> !llvm.ptr
llvm.store %1304, %1306 : i64, !llvm.ptr
cf.br ^bb177
^bb177:
%1307 = llvm.load %1306 : !llvm.ptr -> i64
%1309 = llvm.getelementptr %776[%1302] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1308 = llvm.load %1309 : !llvm.ptr -> i64
%1310 = arith.cmpi slt, %1307, %1308 : i64
cf.cond_br %1310, ^bb178, ^bb179
^bb178:
%1312 = llvm.mlir.addressof @P : !llvm.ptr
%1313 = llvm.load %1312 : !llvm.ptr -> i64
%1314 = arith.muli %1302, %1313 : i64
%1315 = llvm.load %1306 : !llvm.ptr -> i64
%1316 = arith.addi %1314, %1315 : i64
%1317 = llvm.getelementptr %781[%1316] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1311 = llvm.load %1317 : !llvm.ptr -> i64
%1318 = llvm.mlir.addressof @P : !llvm.ptr
%1319 = llvm.load %1318 : !llvm.ptr -> i64
%1320 = arith.muli %1276, %1319 : i64
%1321 = arith.addi %1320, %1311 : i64
%1322 = arith.constant 0 : i32
%1323 = llvm.mlir.constant(1 : i64) : i64
%1324 = llvm.alloca %1323 x i32 : (i64) -> !llvm.ptr
llvm.store %1322, %1324 : i32, !llvm.ptr
%1325 = arith.constant 0 : i32
%1326 = arith.extsi %1325 : i32 to i64
%1327 = llvm.mlir.constant(1 : i64) : i64
%1328 = llvm.alloca %1327 x i64 : (i64) -> !llvm.ptr
llvm.store %1326, %1328 : i64, !llvm.ptr
cf.br ^bb180
^bb180:
%1329 = llvm.load %1328 : !llvm.ptr -> i64
%1330 = llvm.load %1267 : !llvm.ptr -> i64
%1331 = arith.cmpi slt, %1329, %1330 : i64
cf.cond_br %1331, ^bb181, ^bb182
^bb181:
%1333 = llvm.load %1328 : !llvm.ptr -> i64
%1334 = llvm.getelementptr %1259[%1333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1332 = llvm.load %1334 : !llvm.ptr -> i64
%1335 = arith.cmpi eq, %1332, %1321 : i64
cf.cond_br %1335, ^bb183, ^bb184
^bb183:
%1336 = arith.constant 1 : i32
llvm.store %1336, %1324 : i32, !llvm.ptr
cf.br ^bb182
^bb184:
cf.br ^bb185
^bb185:
%1337 = llvm.load %1328 : !llvm.ptr -> i64
%1338 = arith.constant 1 : i32
%1340 = arith.extsi %1338 : i32 to i64
%1339 = arith.addi %1337, %1340 : i64
llvm.store %1339, %1328 : i64, !llvm.ptr
cf.br ^bb180
^bb182:
%1341 = llvm.load %1324 : !llvm.ptr -> i32
%1342 = arith.constant 0 : i32
%1343 = arith.cmpi eq, %1341, %1342 : i32
cf.cond_br %1343, ^bb186, ^bb187
^bb186:
%1344 = llvm.load %1267 : !llvm.ptr -> i64
%1345 = llvm.getelementptr %1259[%1344] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1321, %1345 : i64, !llvm.ptr
%1346 = llvm.load %1267 : !llvm.ptr -> i64
%1347 = arith.constant 1 : i32
%1349 = arith.extsi %1347 : i32 to i64
%1348 = arith.addi %1346, %1349 : i64
llvm.store %1348, %1267 : i64, !llvm.ptr
cf.br ^bb188
^bb187:
cf.br ^bb188
^bb188:
%1350 = llvm.load %1306 : !llvm.ptr -> i64
%1351 = arith.constant 1 : i32
%1353 = arith.extsi %1351 : i32 to i64
%1352 = arith.addi %1350, %1353 : i64
llvm.store %1352, %1306 : i64, !llvm.ptr
cf.br ^bb177
^bb179:
%1354 = llvm.load %1171 : !llvm.ptr -> i64
%1355 = arith.constant 1 : i32
%1357 = arith.extsi %1355 : i32 to i64
%1356 = arith.addi %1354, %1357 : i64
llvm.store %1356, %1171 : i64, !llvm.ptr
cf.br ^bb174
^bb176:
%1358 = arith.constant 0 : i32
%1359 = arith.extsi %1358 : i32 to i64
llvm.store %1359, %1171 : i64, !llvm.ptr
cf.br ^bb189
^bb189:
%1360 = llvm.load %1171 : !llvm.ptr -> i64
%1361 = llvm.load %1267 : !llvm.ptr -> i64
%1362 = arith.cmpi slt, %1360, %1361 : i64
cf.cond_br %1362, ^bb190, ^bb191
^bb190:
%1364 = llvm.load %1171 : !llvm.ptr -> i64
%1365 = llvm.getelementptr %1259[%1364] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1363 = llvm.load %1365 : !llvm.ptr -> i64
%1366 = llvm.load %1171 : !llvm.ptr -> i64
%1367 = llvm.getelementptr %1135[%1366] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1363, %1367 : i64, !llvm.ptr
%1368 = llvm.load %1171 : !llvm.ptr -> i64
%1369 = arith.constant 1 : i32
%1371 = arith.extsi %1369 : i32 to i64
%1370 = arith.addi %1368, %1371 : i64
llvm.store %1370, %1171 : i64, !llvm.ptr
cf.br ^bb189
^bb191:
%1372 = llvm.load %1267 : !llvm.ptr -> i64
%1373 = arith.constant 0 : i32
%1374 = arith.extsi %1373 : i32 to i64
%1375 = llvm.getelementptr %1140[%1374] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %1372, %1375 : i64, !llvm.ptr
func.call @free(%1259) : (!llvm.ptr) -> ()
%1377 = llvm.load %1217 : !llvm.ptr -> i64
%1378 = arith.constant 1 : i32
%1380 = arith.extsi %1378 : i32 to i64
%1379 = arith.addi %1377, %1380 : i64
llvm.store %1379, %1217 : i64, !llvm.ptr
%1381 = llvm.load %1217 : !llvm.ptr -> i64
%1382 = arith.constant 30 : i32
%1384 = arith.extsi %1382 : i32 to i64
%1383 = arith.cmpi sgt, %1381, %1384 : i64
cf.cond_br %1383, ^bb192, ^bb193
^bb192:
cf.br ^bb167
^bb193:
cf.br ^bb194
^bb194:
cf.br ^bb165
^bb167:
%1385 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1386 = llvm.load %1162 : !llvm.ptr -> i64
%1387 = llvm.call @printf(%1385, %1386) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%740) : (!llvm.ptr) -> ()
func.call @free(%754) : (!llvm.ptr) -> ()
func.call @free(%768) : (!llvm.ptr) -> ()
func.call @free(%776) : (!llvm.ptr) -> ()
func.call @free(%781) : (!llvm.ptr) -> ()
func.call @free(%982) : (!llvm.ptr) -> ()
func.call @free(%987) : (!llvm.ptr) -> ()
func.call @free(%1075) : (!llvm.ptr) -> ()
func.call @free(%1080) : (!llvm.ptr) -> ()
func.call @free(%1085) : (!llvm.ptr) -> ()
func.call @free(%1090) : (!llvm.ptr) -> ()
func.call @free(%1095) : (!llvm.ptr) -> ()
func.call @free(%1100) : (!llvm.ptr) -> ()
func.call @free(%1105) : (!llvm.ptr) -> ()
func.call @free(%1110) : (!llvm.ptr) -> ()
func.call @free(%1115) : (!llvm.ptr) -> ()
func.call @free(%1120) : (!llvm.ptr) -> ()
func.call @free(%1125) : (!llvm.ptr) -> ()
func.call @free(%1130) : (!llvm.ptr) -> ()
func.call @free(%1135) : (!llvm.ptr) -> ()
func.call @free(%1140) : (!llvm.ptr) -> ()
%1409 = arith.constant 0 : i32
func.return %1409 : i32
}
}