← All problems Problem 768
Chandelier: f(360, 20) via generating functions over cyclotomic fields. Count arrangements of 20 identical candles in 360 distinct sockets such that the vector sum of the chosen 360th roots of unity is 0. Factorisation 360 = 5 * 8 * 9 and cyclotomic structure reduce the balance constraint to 12 identical independent blocks. For each block we build a generating function S(x) by summing (P_delta(x))^3 over all differences delta of two pentagon-choices, then the answer is [x^20] S(x)^12. Exact integer arithmetic is recovered via CRT over three 64-bit primes.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(sqrt(n))Space complexity O(n^2)O(1)Approach Flow solution Trial division or Pollard rho Verdict Suboptimal
Flow source
# Project Euler 768
# Chandelier: f(360, 20) via generating functions over cyclotomic fields.
#
# Count arrangements of 20 identical candles in 360 distinct sockets such that
# the vector sum of the chosen 360th roots of unity is 0.
#
# Factorisation 360 = 5 * 8 * 9 and cyclotomic structure reduce the balance
# constraint to 12 identical independent blocks. For each block we build a
# generating function S(x) by summing (P_delta(x))^3 over all differences delta
# of two pentagon-choices, then the answer is [x^20] S(x)^12.
#
# Exact integer arithmetic is recovered via CRT over three 64-bit primes.
import euler.nt { mod_pow }
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function memcpy(dst: ptr<void>, src: ptr<void>, n: i64) -> ptr<void>
function memset(p: ptr<void>, v: i32, n: i64) -> ptr<void>
}
const M: i32 = 20
const N: i32 = 21
const P1: i64 = 998244353
const P2: i64 = 1004535809
const P3: i64 = 469762049
function madd(a: i64, b: i64, m: i64) -> i64 {
let r: i64 = a + b
if r >= m { r = r - m }
return r
}
function msub(a: i64, b: i64, m: i64) -> i64 {
let r: i64 = a - b
if r < 0 { r = r + m }
return r
}
function mmul(a: i64, b: i64, m: i64) -> i64 {
return ((a as i128) * (b as i128) % (m as i128)) as i64
}
function minv(a: i64, m: i64) -> i64 {
return mod_pow(a, m - 2, m)
}
# res = a * b truncated to degree M (mod m)
function polymul(res: ptr<i64>, a: ptr<i64>, b: ptr<i64>, mod: i64) -> void {
let tmp: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
for i in 0..N {
if a[i] == 0 { continue }
for j in 0..(N - i) {
if b[j] == 0 { continue }
tmp[i + j] = madd(tmp[i + j], mmul(a[i], b[j], mod), mod)
}
}
memcpy(res as ptr<void>, tmp as ptr<void>, (N as i64) * 8)
free(tmp as ptr<void>)
}
# res = base^exp truncated to degree M (mod m)
function polypow(res: ptr<i64>, base: ptr<i64>, exp0: i32, mod: i64) -> void {
for i in 0..N {
res[i] = 0
}
res[0] = 1 % mod
let cur: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
memcpy(cur as ptr<void>, base as ptr<void>, (N as i64) * 8)
let mut e: i32 = exp0
while e > 0 {
if e % 2 == 1 {
polymul(res, res, cur, mod)
}
e = e / 2
if e != 0 {
polymul(cur, cur, cur, mod)
}
}
free(cur as ptr<void>)
}
struct PairEntry {
key: i32
w: i32
}
# Heapsort for PairEntry array, sorted by key ascending
function sift_down_pairs(arr: ptr<PairEntry>, start: i64, end: i64) -> void {
let mut root: i64 = start
while 2 * root + 1 < end {
let mut child: i64 = 2 * root + 1
if child + 1 < end {
if arr[child].key < arr[child + 1].key {
child = child + 1
}
}
if arr[root].key < arr[child].key {
let tk: i32 = arr[root].key
let tw: i32 = arr[root].w
arr[root].key = arr[child].key
arr[root].w = arr[child].w
arr[child].key = tk
arr[child].w = tw
root = child
} else {
return
}
}
}
function heapsort_pairs(arr: ptr<PairEntry>, n: i64) -> void {
if n < 2 { return }
let mut start: i64 = n / 2
while start > 0 {
start = start - 1
sift_down_pairs(arr, start, n)
}
let mut end: i64 = n
while end > 1 {
end = end - 1
let tk: i32 = arr[0].key
let tw: i32 = arr[0].w
arr[0].key = arr[end].key
arr[0].w = arr[end].w
arr[end].key = tk
arr[end].w = tw
sift_down_pairs(arr, 0, end)
}
}
# Solve f(360,20) modulo one prime.
function solve_mod(mod: i64) -> i64 {
# Build the 32 pentagon-choices (subsets of {1,y,y^2,y^3,y^4}).
let pat_coeff: ptr<i64> = calloc(32 * 4, 8) as ptr<i64>
let pat_cnt: ptr<i32> = calloc(32, 4) as ptr<i32>
for mask in 0..32 {
let coeff: ptr<i64> = calloc(4, 8) as ptr<i64>
let cnt: i32 = 0
for v in 0..5 {
if (mask & (1 << v)) != 0 {
cnt = cnt + 1
if v < 4 {
coeff[v] = coeff[v] + 1
} else {
for k in 0..4 {
coeff[k] = coeff[k] - 1
}
}
}
}
for k in 0..4 {
pat_coeff[mask * 4 + k] = coeff[k]
}
pat_cnt[mask] = cnt
free(coeff as ptr<void>)
}
# Collect all 32*32 ordered pairs, keyed by their 4-tuple difference.
let pairs: ptr<PairEntry> = calloc(1024, 8) as ptr<PairEntry>
let npairs: i32 = 0
for i in 0..32 {
for j in 0..32 {
let d0: i32 = (pat_coeff[i * 4] - pat_coeff[j * 4]) as i32 + 10
let d1: i32 = (pat_coeff[i * 4 + 1] - pat_coeff[j * 4 + 1]) as i32 + 10
let d2: i32 = (pat_coeff[i * 4 + 2] - pat_coeff[j * 4 + 2]) as i32 + 10
let d3: i32 = (pat_coeff[i * 4 + 3] - pat_coeff[j * 4 + 3]) as i32 + 10
let key: i32 = d0 + 21 * d1 + 441 * d2 + 9261 * d3
pairs[npairs].key = key
pairs[npairs].w = pat_cnt[i] + pat_cnt[j]
npairs = npairs + 1
}
}
heapsort_pairs(pairs, npairs as i64)
# Group by delta, cube each P_delta, accumulate into S.
let S: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
let mut idx: i32 = 0
while idx < npairs {
let key: i32 = pairs[idx].key
let P: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
while idx < npairs && pairs[idx].key == key {
let w: i32 = pairs[idx].w
if w <= M {
P[w] = madd(P[w], 1, mod)
}
idx = idx + 1
}
let P2: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
let P3: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
polymul(P2, P, P, mod)
polymul(P3, P2, P, mod)
for i in 0..N {
S[i] = madd(S[i], P3[i], mod)
}
free(P as ptr<void>)
free(P2 as ptr<void>)
free(P3 as ptr<void>)
}
# 12 independent blocks: answer = [x^20] S(x)^12.
let result: ptr<i64> = calloc(N as i64, 8) as ptr<i64>
polypow(result, S, 12, mod)
let ans: i64 = result[M]
free(result as ptr<void>)
free(S as ptr<void>)
free(pairs as ptr<void>)
free(pat_coeff as ptr<void>)
free(pat_cnt as ptr<void>)
return ans
}
# CRT over three primes to recover the exact integer.
function crt3(a1: i64, a2: i64, a3: i64) -> i64 {
let inv12: i64 = minv(P1 % P2, P2)
let P12: i128 = (P1 as i128) * (P2 as i128)
let t1: i64 = msub(a2, a1 % P2, P2)
t1 = mmul(t1, inv12, P2)
let x2: i128 = (a1 as i128) + (P1 as i128) * (t1 as i128)
let inv123: i64 = minv((P12 % P3) as i64, P3)
let t2: i64 = msub(a3, (x2 % P3) as i64, P3)
t2 = mmul(t2, inv123, P3)
let x: i128 = x2 + P12 * (t2 as i128)
return x as i64
}
function main() -> i32 {
let a1: i64 = solve_mod(P1)
let a2: i64 = solve_mod(P2)
let a3: i64 = solve_mod(P3)
printf("%lld\n", crt3(a1, a2, a3))
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; }
typedef struct PairEntry PairEntry;
struct PairEntry {
int32_t key;
int32_t w;
};
int64_t gcd_i64_i64(int64_t a0, int64_t b0);
int64_t lcm_i64_i64(int64_t a, int64_t b);
int64_t isqrt_i64(int64_t n);
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod);
bool is_prime_i64(int64_t n);
int64_t madd_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t msub_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t mmul_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t minv_i64_i64(int64_t a, int64_t m);
void polymul_ptr_i64_ptr_i64_ptr_i64_i64(int64_t* res, int64_t* a, int64_t* b, int64_t mod);
void polypow_ptr_i64_ptr_i64_i32_i64(int64_t* res, int64_t* base, int32_t exp0, int64_t mod);
void sift_down_pairs_ptr_PairEntry_i64_i64(PairEntry* arr, int64_t start, int64_t end);
void heapsort_pairs_ptr_PairEntry_i64(PairEntry* arr, int64_t n);
int64_t solve_mod_i64(int64_t mod);
int64_t crt3_i64_i64_i64(int64_t a1, int64_t a2, int64_t a3);
int32_t main(void);
static const int32_t M = 20;
static const int32_t N = 21;
static const int64_t P1 = 998244353;
static const int64_t P2 = 1004535809;
static const int64_t P3 = 469762049;
int64_t gcd_i64_i64(int64_t a0, int64_t b0) {
int64_t a = a0;
int64_t b = b0;
while (b != 0) {
int64_t t = FLOW_CHECKED_MOD((a), (b));
a = b;
b = t;
}
return a;
}
int64_t lcm_i64_i64(int64_t a, int64_t b) {
if ((a == 0 || b == 0)) {
return 0;
}
return (FLOW_CHECKED_DIV((a), (gcd_i64_i64(a, b))) * b);
}
int64_t isqrt_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t mulmod_i64_i64_i64(int64_t a0, int64_t b0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t b = FLOW_CHECKED_MOD((b0), (mod));
int64_t result = 0;
while (b > 0) {
if (FLOW_CHECKED_MOD((b), (2)) == 1) {
result = FLOW_CHECKED_MOD(((result + a)), (mod));
}
a = FLOW_CHECKED_MOD(((a * 2)), (mod));
b = FLOW_CHECKED_DIV((b), (2));
}
return result;
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t mod) {
if (mod == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (mod));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, mod);
}
b = mulmod_i64_i64_i64(b, b, mod);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
bool is_prime_i64(int64_t n) {
if (n < 2) {
return 0;
}
if (n < 4) {
return 1;
}
if ((FLOW_CHECKED_MOD((n), (2)) == 0 || FLOW_CHECKED_MOD((n), (3)) == 0)) {
return 0;
}
int64_t i = 5;
while ((i * i) <= n) {
if ((FLOW_CHECKED_MOD((n), (i)) == 0 || FLOW_CHECKED_MOD((n), ((i + 2))) == 0)) {
return 0;
}
i = (i + 6);
}
return 1;
}
int64_t madd_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
int64_t r = (a + b);
if (r >= m) {
r = (r - m);
}
return r;
}
int64_t msub_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
int64_t r = (a - b);
if (r < 0) {
r = (r + m);
}
return r;
}
int64_t mmul_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(m))))));
}
int64_t minv_i64_i64(int64_t a, int64_t m) {
return mod_pow_i64_i64_i64(a, (m - 2), m);
}
void polymul_ptr_i64_ptr_i64_ptr_i64_i64(int64_t* res, int64_t* a, int64_t* b, int64_t mod) {
int64_t* tmp = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= N) ? i < N : i > N; i += (0 <= N) ? 1 : -1) {
if (a[i] == 0) {
continue;
}
int32_t __flow_step_2 = 1;
for (int32_t j = 0; (0 <= (N - i)) ? j < (N - i) : j > (N - i); j += (0 <= (N - i)) ? 1 : -1) {
if (b[j] == 0) {
continue;
}
tmp[(i + j)] = madd_i64_i64_i64(tmp[(i + j)], mmul_i64_i64_i64(a[i], b[j], mod), mod);
}
}
memcpy(((void*)(res)), ((void*)(tmp)), (((int64_t)(N)) * 8));
free(((void*)(tmp)));
}
void polypow_ptr_i64_ptr_i64_i32_i64(int64_t* res, int64_t* base, int32_t exp0, int64_t mod) {
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= N) ? i < N : i > N; i += (0 <= N) ? 1 : -1) {
res[i] = 0;
}
res[0] = FLOW_CHECKED_MOD((1), (mod));
int64_t* cur = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
memcpy(((void*)(cur)), ((void*)(base)), (((int64_t)(N)) * 8));
int32_t e = exp0;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
polymul_ptr_i64_ptr_i64_ptr_i64_i64(res, res, cur, mod);
}
e = FLOW_CHECKED_DIV((e), (2));
if (e != 0) {
polymul_ptr_i64_ptr_i64_ptr_i64_i64(cur, cur, cur, mod);
}
}
free(((void*)(cur)));
}
void sift_down_pairs_ptr_PairEntry_i64_i64(PairEntry* arr, int64_t start, int64_t end) {
int64_t root = start;
while (((2 * root) + 1) < end) {
int64_t child = ((2 * root) + 1);
if ((child + 1) < end) {
if (arr[child].key < arr[(child + 1)].key) {
child = (child + 1);
}
}
if (arr[root].key < arr[child].key) {
int32_t tk = arr[root].key;
int32_t tw = arr[root].w;
arr[root].key = arr[child].key;
arr[root].w = arr[child].w;
arr[child].key = tk;
arr[child].w = tw;
root = child;
} else {
return;
}
}
}
void heapsort_pairs_ptr_PairEntry_i64(PairEntry* arr, int64_t n) {
if (n < 2) {
return;
}
int64_t start = FLOW_CHECKED_DIV((n), (2));
while (start > 0) {
start = (start - 1);
sift_down_pairs_ptr_PairEntry_i64_i64(arr, start, n);
}
int64_t end = n;
while (end > 1) {
end = (end - 1);
int32_t tk = arr[0].key;
int32_t tw = arr[0].w;
arr[0].key = arr[end].key;
arr[0].w = arr[end].w;
arr[end].key = tk;
arr[end].w = tw;
sift_down_pairs_ptr_PairEntry_i64_i64(arr, 0, end);
}
}
int64_t solve_mod_i64(int64_t mod) {
int64_t* pat_coeff = (int64_t*)(((int64_t*)(calloc((32 * 4), 8))));
int32_t* pat_cnt = (int32_t*)(((int32_t*)(calloc(32, 4))));
int32_t __flow_step_4 = 1;
for (int32_t mask = 0; (0 <= 32) ? mask < 32 : mask > 32; mask += (0 <= 32) ? 1 : -1) {
int64_t* coeff = (int64_t*)(((int64_t*)(calloc(4, 8))));
int32_t cnt = 0;
int32_t __flow_step_5 = 1;
for (int32_t v = 0; (0 <= 5) ? v < 5 : v > 5; v += (0 <= 5) ? 1 : -1) {
if ((mask & FLOW_CHECKED_SHL((1), (v))) != 0) {
cnt = (cnt + 1);
if (v < 4) {
coeff[v] = (coeff[v] + 1);
} else {
int32_t __flow_step_6 = 1;
for (int32_t k = 0; (0 <= 4) ? k < 4 : k > 4; k += (0 <= 4) ? 1 : -1) {
coeff[k] = (coeff[k] - 1);
}
}
}
}
int32_t __flow_step_7 = 1;
for (int32_t k = 0; (0 <= 4) ? k < 4 : k > 4; k += (0 <= 4) ? 1 : -1) {
pat_coeff[((mask * 4) + k)] = coeff[k];
}
pat_cnt[mask] = cnt;
free(((void*)(coeff)));
}
PairEntry* pairs = (PairEntry*)(((PairEntry*)(calloc(1024, 8))));
int32_t npairs = 0;
int32_t __flow_step_8 = 1;
for (int32_t i = 0; (0 <= 32) ? i < 32 : i > 32; i += (0 <= 32) ? 1 : -1) {
int32_t __flow_step_9 = 1;
for (int32_t j = 0; (0 <= 32) ? j < 32 : j > 32; j += (0 <= 32) ? 1 : -1) {
int32_t d0 = (((int32_t)((pat_coeff[(i * 4)] - pat_coeff[(j * 4)]))) + 10);
int32_t d1 = (((int32_t)((pat_coeff[((i * 4) + 1)] - pat_coeff[((j * 4) + 1)]))) + 10);
int32_t d2 = (((int32_t)((pat_coeff[((i * 4) + 2)] - pat_coeff[((j * 4) + 2)]))) + 10);
int32_t d3 = (((int32_t)((pat_coeff[((i * 4) + 3)] - pat_coeff[((j * 4) + 3)]))) + 10);
int32_t key = (((d0 + (21 * d1)) + (441 * d2)) + (9261 * d3));
pairs[npairs].key = key;
pairs[npairs].w = (pat_cnt[i] + pat_cnt[j]);
npairs = (npairs + 1);
}
}
heapsort_pairs_ptr_PairEntry_i64(pairs, ((int64_t)(npairs)));
int64_t* S = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
int32_t idx = 0;
while (idx < npairs) {
int32_t key = pairs[idx].key;
int64_t* P = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
while ((idx < npairs && pairs[idx].key == key)) {
int32_t w = pairs[idx].w;
if (w <= M) {
P[w] = madd_i64_i64_i64(P[w], 1, mod);
}
idx = (idx + 1);
}
int64_t* P2 = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
int64_t* P3 = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
polymul_ptr_i64_ptr_i64_ptr_i64_i64(P2, P, P, mod);
polymul_ptr_i64_ptr_i64_ptr_i64_i64(P3, P2, P, mod);
int32_t __flow_step_10 = 1;
for (int32_t i = 0; (0 <= N) ? i < N : i > N; i += (0 <= N) ? 1 : -1) {
S[i] = madd_i64_i64_i64(S[i], P3[i], mod);
}
free(((void*)(P)));
free(((void*)(P2)));
free(((void*)(P3)));
}
int64_t* result = (int64_t*)(((int64_t*)(calloc(((int64_t)(N)), 8))));
polypow_ptr_i64_ptr_i64_i32_i64(result, S, 12, mod);
int64_t ans = result[M];
free(((void*)(result)));
free(((void*)(S)));
free(((void*)(pairs)));
free(((void*)(pat_coeff)));
free(((void*)(pat_cnt)));
return ans;
}
int64_t crt3_i64_i64_i64(int64_t a1, int64_t a2, int64_t a3) {
int64_t inv12 = minv_i64_i64(FLOW_CHECKED_MOD((P1), (P2)), P2);
__int128 P12 = (((__int128)(P1)) * ((__int128)(P2)));
int64_t t1 = msub_i64_i64_i64(a2, FLOW_CHECKED_MOD((a1), (P2)), P2);
t1 = mmul_i64_i64_i64(t1, inv12, P2);
__int128 x2 = (((__int128)(a1)) + (((__int128)(P1)) * ((__int128)(t1))));
int64_t inv123 = minv_i64_i64(((int64_t)(FLOW_CHECKED_MOD((P12), (P3)))), P3);
int64_t t2 = msub_i64_i64_i64(a3, ((int64_t)(FLOW_CHECKED_MOD((x2), (P3)))), P3);
t2 = mmul_i64_i64_i64(t2, inv123, P3);
__int128 x = (x2 + (P12 * ((__int128)(t2))));
return ((int64_t)(x));
}
int32_t main(void) {
int64_t a1 = solve_mod_i64(P1);
int64_t a2 = solve_mod_i64(P2);
int64_t a3 = solve_mod_i64(P3);
printf("%lld\n", crt3_i64_i64_i64(a1, a2, a3));
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 @gcd(%arg0: i64, %arg1: i64) -> i64 {
%0 = llvm.mlir.constant(1 : i64) : i64
%1 = llvm.alloca %0 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %1 : i64, !llvm.ptr
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @lcm(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 0 : i32
%15 = arith.extsi %13 : i32 to i64
%14 = arith.cmpi eq, %arg0, %15 : i64
%16 = scf.if %14 -> (i1) {
%17 = arith.constant true
scf.yield %17 : i1
} else {
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %arg1, %20 : i64
scf.yield %19 : i1
}
cf.cond_br %16, ^bb3, ^bb4
^bb3:
%21 = arith.constant 0 : i32
%22 = arith.extsi %21 : i32 to i64
func.return %22 : i64
^bb4:
cf.br ^bb5
^bb5:
%23 = func.call @gcd(%arg0, %arg1) : (i64, i64) -> i64
%24 = arith.divsi %arg0, %23 : i64
%25 = arith.muli %24, %arg1 : i64
func.return %25 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%26 = arith.constant 2 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
func.return %arg0 : i64
^bb7:
cf.br ^bb8
^bb8:
%29 = llvm.mlir.constant(1 : i64) : i64
%30 = llvm.alloca %29 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %30 : i64, !llvm.ptr
%31 = llvm.load %30 : !llvm.ptr -> i64
%32 = arith.constant 1 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.addi %31, %34 : i64
%35 = arith.constant 2 : i32
%37 = arith.extsi %35 : i32 to i64
%36 = arith.divsi %33, %37 : i64
%38 = llvm.mlir.constant(1 : i64) : i64
%39 = llvm.alloca %38 x i64 : (i64) -> !llvm.ptr
llvm.store %36, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%40 = llvm.load %39 : !llvm.ptr -> i64
%41 = llvm.load %30 : !llvm.ptr -> i64
%42 = arith.cmpi slt, %40, %41 : i64
cf.cond_br %42, ^bb10, ^bb11
^bb10:
%43 = llvm.load %39 : !llvm.ptr -> i64
llvm.store %43, %30 : i64, !llvm.ptr
%44 = llvm.load %30 : !llvm.ptr -> i64
%45 = llvm.load %30 : !llvm.ptr -> i64
%46 = arith.divsi %arg0, %45 : i64
%47 = arith.addi %44, %46 : i64
%48 = arith.constant 2 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.divsi %47, %50 : i64
llvm.store %49, %39 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%51 = llvm.load %30 : !llvm.ptr -> i64
func.return %51 : i64
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%52 = arith.remsi %arg0, %arg2 : i64
%53 = llvm.mlir.constant(1 : i64) : i64
%54 = llvm.alloca %53 x i64 : (i64) -> !llvm.ptr
llvm.store %52, %54 : i64, !llvm.ptr
%55 = arith.remsi %arg1, %arg2 : i64
%56 = llvm.mlir.constant(1 : i64) : i64
%57 = llvm.alloca %56 x i64 : (i64) -> !llvm.ptr
llvm.store %55, %57 : i64, !llvm.ptr
%58 = arith.constant 0 : i32
%59 = arith.extsi %58 : i32 to i64
%60 = llvm.mlir.constant(1 : i64) : i64
%61 = llvm.alloca %60 x i64 : (i64) -> !llvm.ptr
llvm.store %59, %61 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%62 = llvm.load %57 : !llvm.ptr -> i64
%63 = arith.constant 0 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.cmpi sgt, %62, %65 : i64
cf.cond_br %64, ^bb13, ^bb14
^bb13:
%66 = llvm.load %57 : !llvm.ptr -> i64
%67 = arith.constant 2 : i32
%69 = arith.extsi %67 : i32 to i64
%68 = arith.remsi %66, %69 : i64
%70 = arith.constant 1 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi eq, %68, %72 : i64
cf.cond_br %71, ^bb15, ^bb16
^bb15:
%73 = llvm.load %61 : !llvm.ptr -> i64
%74 = llvm.load %54 : !llvm.ptr -> i64
%75 = arith.addi %73, %74 : i64
%76 = arith.remsi %75, %arg2 : i64
llvm.store %76, %61 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%77 = llvm.load %54 : !llvm.ptr -> i64
%78 = arith.constant 2 : i32
%80 = arith.extsi %78 : i32 to i64
%79 = arith.muli %77, %80 : i64
%81 = arith.remsi %79, %arg2 : i64
llvm.store %81, %54 : i64, !llvm.ptr
%82 = llvm.load %57 : !llvm.ptr -> i64
%83 = arith.constant 2 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.divsi %82, %85 : i64
llvm.store %84, %57 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%86 = llvm.load %61 : !llvm.ptr -> i64
func.return %86 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%87 = arith.constant 1 : i32
%89 = arith.extsi %87 : i32 to i64
%88 = arith.cmpi eq, %arg2, %89 : i64
cf.cond_br %88, ^bb18, ^bb19
^bb18:
%90 = arith.constant 0 : i32
%91 = arith.extsi %90 : i32 to i64
func.return %91 : i64
^bb19:
cf.br ^bb20
^bb20:
%92 = arith.constant 1 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.mlir.constant(1 : i64) : i64
%95 = llvm.alloca %94 x i64 : (i64) -> !llvm.ptr
llvm.store %93, %95 : i64, !llvm.ptr
%96 = arith.remsi %arg0, %arg2 : i64
%97 = llvm.mlir.constant(1 : i64) : i64
%98 = llvm.alloca %97 x i64 : (i64) -> !llvm.ptr
llvm.store %96, %98 : i64, !llvm.ptr
%99 = llvm.mlir.constant(1 : i64) : i64
%100 = llvm.alloca %99 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.constant 0 : i32
%104 = arith.extsi %102 : i32 to i64
%103 = arith.cmpi sgt, %101, %104 : i64
cf.cond_br %103, ^bb22, ^bb23
^bb22:
%105 = llvm.load %100 : !llvm.ptr -> i64
%106 = arith.constant 2 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %105, %108 : i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.cmpi eq, %107, %111 : i64
cf.cond_br %110, ^bb24, ^bb25
^bb24:
%113 = llvm.load %95 : !llvm.ptr -> i64
%114 = llvm.load %98 : !llvm.ptr -> i64
%112 = func.call @mulmod(%113, %114, %arg2) : (i64, i64, i64) -> i64
llvm.store %112, %95 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%116 = llvm.load %98 : !llvm.ptr -> i64
%117 = llvm.load %98 : !llvm.ptr -> i64
%115 = func.call @mulmod(%116, %117, %arg2) : (i64, i64, i64) -> i64
llvm.store %115, %98 : i64, !llvm.ptr
%118 = llvm.load %100 : !llvm.ptr -> i64
%119 = arith.constant 2 : i32
%121 = arith.extsi %119 : i32 to i64
%120 = arith.divsi %118, %121 : i64
llvm.store %120, %100 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%122 = llvm.load %95 : !llvm.ptr -> i64
func.return %122 : i64
}
func.func @is_prime(%arg0: i64) -> i1 {
%123 = arith.constant 2 : i32
%125 = arith.extsi %123 : i32 to i64
%124 = arith.cmpi slt, %arg0, %125 : i64
cf.cond_br %124, ^bb27, ^bb28
^bb27:
%126 = arith.constant 0 : i1
func.return %126 : i1
^bb28:
cf.br ^bb29
^bb29:
%127 = arith.constant 4 : i32
%129 = arith.extsi %127 : i32 to i64
%128 = arith.cmpi slt, %arg0, %129 : i64
cf.cond_br %128, ^bb30, ^bb31
^bb30:
%130 = arith.constant 1 : i1
func.return %130 : i1
^bb31:
cf.br ^bb32
^bb32:
%131 = arith.constant 2 : i32
%133 = arith.extsi %131 : i32 to i64
%132 = arith.remsi %arg0, %133 : i64
%134 = arith.constant 0 : i32
%136 = arith.extsi %134 : i32 to i64
%135 = arith.cmpi eq, %132, %136 : i64
%137 = scf.if %135 -> (i1) {
%138 = arith.constant true
scf.yield %138 : i1
} else {
%139 = arith.constant 3 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.remsi %arg0, %141 : i64
%142 = arith.constant 0 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.cmpi eq, %140, %144 : i64
scf.yield %143 : i1
}
cf.cond_br %137, ^bb33, ^bb34
^bb33:
%145 = arith.constant 0 : i1
func.return %145 : i1
^bb34:
cf.br ^bb35
^bb35:
%146 = arith.constant 5 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %149 : !llvm.ptr -> i64
%152 = arith.muli %150, %151 : i64
%153 = arith.cmpi sle, %152, %arg0 : i64
cf.cond_br %153, ^bb37, ^bb38
^bb37:
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = arith.remsi %arg0, %154 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %155, %158 : i64
%159 = scf.if %157 -> (i1) {
%160 = arith.constant true
scf.yield %160 : i1
} else {
%161 = llvm.load %149 : !llvm.ptr -> i64
%162 = arith.constant 2 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.addi %161, %164 : i64
%165 = arith.remsi %arg0, %163 : i64
%166 = arith.constant 0 : i32
%168 = arith.extsi %166 : i32 to i64
%167 = arith.cmpi eq, %165, %168 : i64
scf.yield %167 : i1
}
cf.cond_br %159, ^bb39, ^bb40
^bb39:
%169 = arith.constant 0 : i1
func.return %169 : i1
^bb40:
cf.br ^bb41
^bb41:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = arith.constant 6 : i32
%173 = arith.extsi %171 : i32 to i64
%172 = arith.addi %170, %173 : i64
llvm.store %172, %149 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%174 = arith.constant 1 : i1
func.return %174 : i1
}
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func private @memcpy(!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.func private @memset(!llvm.ptr, i32, i64) -> !llvm.ptr
// Constant: M
llvm.mlir.global internal constant @M(20 : i32) : i32
// Constant: N
llvm.mlir.global internal constant @N(21 : i32) : i32
// Constant: P1
llvm.mlir.global internal constant @P1(998244353 : i64) : i64
// Constant: P2
llvm.mlir.global internal constant @P2(1004535809 : i64) : i64
// Constant: P3
llvm.mlir.global internal constant @P3(469762049 : i64) : i64
func.func @madd(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%175 = arith.addi %arg0, %arg1 : i64
%176 = arith.cmpi sge, %175, %arg2 : i64
%177 = scf.if %176 -> (i64) {
%178 = arith.subi %175, %arg2 : i64
scf.yield %178 : i64
} else {
scf.yield %175 : i64
}
func.return %177 : i64
}
func.func @msub(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%179 = arith.subi %arg0, %arg1 : i64
%180 = arith.constant 0 : i32
%182 = arith.extsi %180 : i32 to i64
%181 = arith.cmpi slt, %179, %182 : i64
%183 = scf.if %181 -> (i64) {
%184 = arith.addi %179, %arg2 : i64
scf.yield %184 : i64
} else {
scf.yield %179 : i64
}
func.return %183 : i64
}
func.func @mmul(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%185 = arith.extsi %arg0 : i64 to i128
%186 = arith.extsi %arg1 : i64 to i128
%188 = arith.trunci %185 : i128 to i64
%189 = arith.trunci %186 : i128 to i64
%187 = arith.muli %188, %189 : i64
%190 = arith.extsi %arg2 : i64 to i128
%192 = arith.trunci %190 : i128 to i64
%191 = arith.remsi %187, %192 : i64
func.return %191 : i64
}
func.func @minv(%arg0: i64, %arg1: i64) -> i64 {
%194 = arith.constant 2 : i32
%196 = arith.extsi %194 : i32 to i64
%195 = arith.subi %arg1, %196 : i64
%193 = func.call @mod_pow(%arg0, %195, %arg1) : (i64, i64, i64) -> i64
func.return %193 : i64
}
func.func @polymul(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: !llvm.ptr, %arg3: i64) -> () {
%198 = llvm.mlir.addressof @N : !llvm.ptr
%199 = llvm.load %198 : !llvm.ptr -> i32
%200 = arith.extsi %199 : i32 to i64
%201 = arith.constant 8 : i32
%202 = arith.extsi %201 : i32 to i64
%197 = func.call @calloc(%200, %202) : (i64, i64) -> !llvm.ptr
%203 = arith.constant 0 : i32
%204 = llvm.mlir.addressof @N : !llvm.ptr
%205 = llvm.load %204 : !llvm.ptr -> i32
%206 = arith.index_cast %203 : i32 to index
%207 = arith.index_cast %205 : i32 to index
%209 = arith.constant 1 : index
%210 = arith.constant -1 : index
%211 = arith.cmpi sle, %206, %207 : index
%208 = arith.select %211, %209, %210 : index
cf.br ^bb42(%206 : index)
^bb42(%212: index):
%213 = arith.cmpi slt, %212, %207 : index
%214 = arith.cmpi sgt, %212, %207 : index
%215 = arith.select %211, %213, %214 : i1
cf.cond_br %215, ^bb43(%212 : index), ^bb44(%212 : index)
^bb43(%216: index):
%218 = arith.index_cast %216 : index to i64
%219 = llvm.getelementptr %arg1[%218] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%217 = llvm.load %219 : !llvm.ptr -> i64
%220 = arith.constant 0 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.cmpi eq, %217, %222 : i64
cf.cond_br %221, ^bb45, ^bb46
^bb45:
%223 = arith.addi %216, %208 : index
cf.br ^bb42(%223 : index)
^bb46:
cf.br ^bb47
^bb47:
%224 = arith.constant 0 : i32
%225 = llvm.mlir.addressof @N : !llvm.ptr
%226 = llvm.load %225 : !llvm.ptr -> i32
%228 = arith.index_cast %216 : index to i32
%227 = arith.subi %226, %228 : i32
%229 = arith.index_cast %224 : i32 to index
%230 = arith.index_cast %227 : i32 to index
%232 = arith.constant 1 : index
%233 = arith.constant -1 : index
%234 = arith.cmpi sle, %229, %230 : index
%231 = arith.select %234, %232, %233 : index
cf.br ^bb48(%229 : index)
^bb48(%235: index):
%236 = arith.cmpi slt, %235, %230 : index
%237 = arith.cmpi sgt, %235, %230 : index
%238 = arith.select %234, %236, %237 : i1
cf.cond_br %238, ^bb49(%235 : index), ^bb50(%235 : index)
^bb49(%239: index):
%241 = arith.index_cast %239 : index to i64
%242 = llvm.getelementptr %arg2[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%240 = llvm.load %242 : !llvm.ptr -> i64
%243 = arith.constant 0 : i32
%245 = arith.extsi %243 : i32 to i64
%244 = arith.cmpi eq, %240, %245 : i64
cf.cond_br %244, ^bb51, ^bb52
^bb51:
%246 = arith.addi %239, %231 : index
cf.br ^bb48(%246 : index)
^bb52:
cf.br ^bb53
^bb53:
%249 = arith.addi %216, %239 : index
%250 = arith.index_cast %249 : index to i64
%251 = llvm.getelementptr %197[%250] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%248 = llvm.load %251 : !llvm.ptr -> i64
%254 = arith.index_cast %216 : index to i64
%255 = llvm.getelementptr %arg1[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%253 = llvm.load %255 : !llvm.ptr -> i64
%257 = arith.index_cast %239 : index to i64
%258 = llvm.getelementptr %arg2[%257] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%256 = llvm.load %258 : !llvm.ptr -> i64
%252 = func.call @mmul(%253, %256, %arg3) : (i64, i64, i64) -> i64
%247 = func.call @madd(%248, %252, %arg3) : (i64, i64, i64) -> i64
%259 = arith.addi %216, %239 : index
%260 = arith.index_cast %259 : index to i64
%261 = llvm.getelementptr %197[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %247, %261 : i64, !llvm.ptr
%262 = arith.addi %239, %231 : index
cf.br ^bb48(%262 : index)
^bb50(%263: index):
%264 = arith.addi %216, %208 : index
cf.br ^bb42(%264 : index)
^bb44(%265: index):
%267 = llvm.mlir.addressof @N : !llvm.ptr
%268 = llvm.load %267 : !llvm.ptr -> i32
%269 = arith.extsi %268 : i32 to i64
%270 = arith.constant 8 : i32
%272 = arith.extsi %270 : i32 to i64
%271 = arith.muli %269, %272 : i64
%266 = func.call @memcpy(%arg0, %197, %271) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
func.call @free(%197) : (!llvm.ptr) -> ()
func.return
}
func.func @polypow(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: i64) -> () {
%274 = arith.constant 0 : i32
%275 = llvm.mlir.addressof @N : !llvm.ptr
%276 = llvm.load %275 : !llvm.ptr -> i32
%277 = arith.index_cast %274 : i32 to index
%278 = arith.index_cast %276 : i32 to index
%280 = arith.constant 1 : index
%281 = arith.constant -1 : index
%282 = arith.cmpi sle, %277, %278 : index
%279 = arith.select %282, %280, %281 : index
cf.br ^bb54(%277 : index)
^bb54(%283: index):
%284 = arith.cmpi slt, %283, %278 : index
%285 = arith.cmpi sgt, %283, %278 : index
%286 = arith.select %282, %284, %285 : i1
cf.cond_br %286, ^bb55(%283 : index), ^bb56(%283 : index)
^bb55(%287: index):
%288 = arith.constant 0 : i32
%289 = arith.extsi %288 : i32 to i64
%290 = arith.index_cast %287 : index to i64
%291 = llvm.getelementptr %arg0[%290] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %289, %291 : i64, !llvm.ptr
%292 = arith.addi %287, %279 : index
cf.br ^bb54(%292 : index)
^bb56(%293: index):
%294 = arith.constant 1 : i32
%296 = arith.extsi %294 : i32 to i64
%295 = arith.remsi %296, %arg3 : i64
%297 = arith.constant 0 : i32
%298 = arith.extsi %297 : i32 to i64
%299 = llvm.getelementptr %arg0[%298] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %295, %299 : i64, !llvm.ptr
%301 = llvm.mlir.addressof @N : !llvm.ptr
%302 = llvm.load %301 : !llvm.ptr -> i32
%303 = arith.extsi %302 : i32 to i64
%304 = arith.constant 8 : i32
%305 = arith.extsi %304 : i32 to i64
%300 = func.call @calloc(%303, %305) : (i64, i64) -> !llvm.ptr
%307 = llvm.mlir.addressof @N : !llvm.ptr
%308 = llvm.load %307 : !llvm.ptr -> i32
%309 = arith.extsi %308 : i32 to i64
%310 = arith.constant 8 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.muli %309, %312 : i64
%306 = func.call @memcpy(%300, %arg1, %311) : (!llvm.ptr, !llvm.ptr, i64) -> !llvm.ptr
%313 = llvm.mlir.constant(1 : i64) : i64
%314 = llvm.alloca %313 x i32 : (i64) -> !llvm.ptr
llvm.store %arg2, %314 : i32, !llvm.ptr
cf.br ^bb57
^bb57:
%315 = llvm.load %314 : !llvm.ptr -> i32
%316 = arith.constant 0 : i32
%317 = arith.cmpi sgt, %315, %316 : i32
cf.cond_br %317, ^bb58, ^bb59
^bb58:
%318 = llvm.load %314 : !llvm.ptr -> i32
%319 = arith.constant 2 : i32
%320 = arith.remsi %318, %319 : i32
%321 = arith.constant 1 : i32
%322 = arith.cmpi eq, %320, %321 : i32
cf.cond_br %322, ^bb60, ^bb61
^bb60:
func.call @polymul(%arg0, %arg0, %300, %arg3) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%324 = llvm.load %314 : !llvm.ptr -> i32
%325 = arith.constant 2 : i32
%326 = arith.divsi %324, %325 : i32
llvm.store %326, %314 : i32, !llvm.ptr
%327 = llvm.load %314 : !llvm.ptr -> i32
%328 = arith.constant 0 : i32
%329 = arith.cmpi ne, %327, %328 : i32
cf.cond_br %329, ^bb63, ^bb64
^bb63:
func.call @polymul(%300, %300, %300, %arg3) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
cf.br ^bb65
^bb64:
cf.br ^bb65
^bb65:
cf.br ^bb57
^bb59:
func.call @free(%300) : (!llvm.ptr) -> ()
func.return
}
// Struct: PairEntry
// Fields:
// key: i32
// w: i32
func.func @sift_down_pairs(%arg0: !llvm.ptr, %arg1: i64, %arg2: i64) -> () {
%332 = llvm.mlir.constant(1 : i64) : i64
%333 = llvm.alloca %332 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %333 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%334 = arith.constant 2 : i32
%335 = llvm.load %333 : !llvm.ptr -> i64
%337 = arith.extsi %334 : i32 to i64
%336 = arith.muli %337, %335 : i64
%338 = arith.constant 1 : i32
%340 = arith.extsi %338 : i32 to i64
%339 = arith.addi %336, %340 : i64
%341 = arith.cmpi slt, %339, %arg2 : i64
cf.cond_br %341, ^bb67, ^bb68
^bb67:
%342 = arith.constant 2 : i32
%343 = llvm.load %333 : !llvm.ptr -> i64
%345 = arith.extsi %342 : i32 to i64
%344 = arith.muli %345, %343 : i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.addi %344, %348 : i64
%349 = llvm.mlir.constant(1 : i64) : i64
%350 = llvm.alloca %349 x i64 : (i64) -> !llvm.ptr
llvm.store %347, %350 : i64, !llvm.ptr
%351 = llvm.load %350 : !llvm.ptr -> i64
%352 = arith.constant 1 : i32
%354 = arith.extsi %352 : i32 to i64
%353 = arith.addi %351, %354 : i64
%355 = arith.cmpi slt, %353, %arg2 : i64
cf.cond_br %355, ^bb69, ^bb70
^bb69:
%357 = llvm.load %350 : !llvm.ptr -> i64
%358 = llvm.getelementptr %arg0[%357] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%356 = llvm.load %358 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%359 = llvm.load %350 : !llvm.ptr -> i64
%360 = llvm.getelementptr %arg0[%359] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%361 = llvm.getelementptr %360[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%362 = llvm.load %361 : !llvm.ptr -> i32
%364 = llvm.load %350 : !llvm.ptr -> i64
%365 = arith.constant 1 : i32
%367 = arith.extsi %365 : i32 to i64
%366 = arith.addi %364, %367 : i64
%368 = llvm.getelementptr %arg0[%366] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%363 = llvm.load %368 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%369 = llvm.load %350 : !llvm.ptr -> i64
%370 = arith.constant 1 : i32
%372 = arith.extsi %370 : i32 to i64
%371 = arith.addi %369, %372 : i64
%373 = llvm.getelementptr %arg0[%371] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%374 = llvm.getelementptr %373[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%375 = llvm.load %374 : !llvm.ptr -> i32
%376 = arith.cmpi slt, %362, %375 : i32
cf.cond_br %376, ^bb72, ^bb73
^bb72:
%377 = llvm.load %350 : !llvm.ptr -> i64
%378 = arith.constant 1 : i32
%380 = arith.extsi %378 : i32 to i64
%379 = arith.addi %377, %380 : i64
llvm.store %379, %350 : i64, !llvm.ptr
cf.br ^bb74
^bb73:
cf.br ^bb74
^bb74:
cf.br ^bb71
^bb70:
cf.br ^bb71
^bb71:
%382 = llvm.load %333 : !llvm.ptr -> i64
%383 = llvm.getelementptr %arg0[%382] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%381 = llvm.load %383 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%384 = llvm.load %333 : !llvm.ptr -> i64
%385 = llvm.getelementptr %arg0[%384] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%386 = llvm.getelementptr %385[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%387 = llvm.load %386 : !llvm.ptr -> i32
%389 = llvm.load %350 : !llvm.ptr -> i64
%390 = llvm.getelementptr %arg0[%389] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%388 = llvm.load %390 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%391 = llvm.load %350 : !llvm.ptr -> i64
%392 = llvm.getelementptr %arg0[%391] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%393 = llvm.getelementptr %392[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%394 = llvm.load %393 : !llvm.ptr -> i32
%395 = arith.cmpi slt, %387, %394 : i32
cf.cond_br %395, ^bb75, ^bb76
^bb75:
%397 = llvm.load %333 : !llvm.ptr -> i64
%398 = llvm.getelementptr %arg0[%397] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%396 = llvm.load %398 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%399 = llvm.load %333 : !llvm.ptr -> i64
%400 = llvm.getelementptr %arg0[%399] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%401 = llvm.getelementptr %400[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%402 = llvm.load %401 : !llvm.ptr -> i32
%404 = llvm.load %333 : !llvm.ptr -> i64
%405 = llvm.getelementptr %arg0[%404] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%403 = llvm.load %405 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%406 = llvm.load %333 : !llvm.ptr -> i64
%407 = llvm.getelementptr %arg0[%406] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%408 = llvm.getelementptr %407[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%409 = llvm.load %408 : !llvm.ptr -> i32
%411 = llvm.load %350 : !llvm.ptr -> i64
%412 = llvm.getelementptr %arg0[%411] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%410 = llvm.load %412 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%413 = llvm.load %350 : !llvm.ptr -> i64
%414 = llvm.getelementptr %arg0[%413] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%415 = llvm.getelementptr %414[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%416 = llvm.load %415 : !llvm.ptr -> i32
%417 = llvm.load %333 : !llvm.ptr -> i64
%418 = llvm.getelementptr %arg0[%417] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%419 = llvm.getelementptr %418[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %416, %419 : i32, !llvm.ptr
%421 = llvm.load %350 : !llvm.ptr -> i64
%422 = llvm.getelementptr %arg0[%421] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%420 = llvm.load %422 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%423 = llvm.load %350 : !llvm.ptr -> i64
%424 = llvm.getelementptr %arg0[%423] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%425 = llvm.getelementptr %424[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%426 = llvm.load %425 : !llvm.ptr -> i32
%427 = llvm.load %333 : !llvm.ptr -> i64
%428 = llvm.getelementptr %arg0[%427] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%429 = llvm.getelementptr %428[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %426, %429 : i32, !llvm.ptr
%430 = llvm.load %350 : !llvm.ptr -> i64
%431 = llvm.getelementptr %arg0[%430] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%432 = llvm.getelementptr %431[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %402, %432 : i32, !llvm.ptr
%433 = llvm.load %350 : !llvm.ptr -> i64
%434 = llvm.getelementptr %arg0[%433] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%435 = llvm.getelementptr %434[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %409, %435 : i32, !llvm.ptr
%436 = llvm.load %350 : !llvm.ptr -> i64
llvm.store %436, %333 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
func.return
^bb77:
cf.br ^bb66
^bb68:
func.return
}
func.func @heapsort_pairs(%arg0: !llvm.ptr, %arg1: i64) -> () {
%437 = arith.constant 2 : i32
%439 = arith.extsi %437 : i32 to i64
%438 = arith.cmpi slt, %arg1, %439 : i64
cf.cond_br %438, ^bb78, ^bb79
^bb78:
func.return
^bb79:
cf.br ^bb80
^bb80:
%440 = arith.constant 2 : i32
%442 = arith.extsi %440 : i32 to i64
%441 = arith.divsi %arg1, %442 : i64
%443 = llvm.mlir.constant(1 : i64) : i64
%444 = llvm.alloca %443 x i64 : (i64) -> !llvm.ptr
llvm.store %441, %444 : i64, !llvm.ptr
cf.br ^bb81
^bb81:
%445 = llvm.load %444 : !llvm.ptr -> i64
%446 = arith.constant 0 : i32
%448 = arith.extsi %446 : i32 to i64
%447 = arith.cmpi sgt, %445, %448 : i64
cf.cond_br %447, ^bb82, ^bb83
^bb82:
%449 = llvm.load %444 : !llvm.ptr -> i64
%450 = arith.constant 1 : i32
%452 = arith.extsi %450 : i32 to i64
%451 = arith.subi %449, %452 : i64
llvm.store %451, %444 : i64, !llvm.ptr
%454 = llvm.load %444 : !llvm.ptr -> i64
func.call @sift_down_pairs(%arg0, %454, %arg1) : (!llvm.ptr, i64, i64) -> ()
cf.br ^bb81
^bb83:
%455 = llvm.mlir.constant(1 : i64) : i64
%456 = llvm.alloca %455 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %456 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%457 = llvm.load %456 : !llvm.ptr -> i64
%458 = arith.constant 1 : i32
%460 = arith.extsi %458 : i32 to i64
%459 = arith.cmpi sgt, %457, %460 : i64
cf.cond_br %459, ^bb85, ^bb86
^bb85:
%461 = llvm.load %456 : !llvm.ptr -> i64
%462 = arith.constant 1 : i32
%464 = arith.extsi %462 : i32 to i64
%463 = arith.subi %461, %464 : i64
llvm.store %463, %456 : i64, !llvm.ptr
%466 = arith.constant 0 : i32
%467 = arith.extsi %466 : i32 to i64
%468 = llvm.getelementptr %arg0[%467] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%465 = llvm.load %468 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%469 = arith.constant 0 : i32
%470 = arith.extsi %469 : i32 to i64
%471 = llvm.getelementptr %arg0[%470] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%472 = llvm.getelementptr %471[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%473 = llvm.load %472 : !llvm.ptr -> i32
%475 = arith.constant 0 : i32
%476 = arith.extsi %475 : i32 to i64
%477 = llvm.getelementptr %arg0[%476] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%474 = llvm.load %477 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%478 = arith.constant 0 : i32
%479 = arith.extsi %478 : i32 to i64
%480 = llvm.getelementptr %arg0[%479] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%481 = llvm.getelementptr %480[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%482 = llvm.load %481 : !llvm.ptr -> i32
%484 = llvm.load %456 : !llvm.ptr -> i64
%485 = llvm.getelementptr %arg0[%484] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%483 = llvm.load %485 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%486 = llvm.load %456 : !llvm.ptr -> i64
%487 = llvm.getelementptr %arg0[%486] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%488 = llvm.getelementptr %487[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%489 = llvm.load %488 : !llvm.ptr -> i32
%490 = arith.constant 0 : i32
%491 = arith.extsi %490 : i32 to i64
%492 = llvm.getelementptr %arg0[%491] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%493 = llvm.getelementptr %492[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %489, %493 : i32, !llvm.ptr
%495 = llvm.load %456 : !llvm.ptr -> i64
%496 = llvm.getelementptr %arg0[%495] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%494 = llvm.load %496 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%497 = llvm.load %456 : !llvm.ptr -> i64
%498 = llvm.getelementptr %arg0[%497] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%499 = llvm.getelementptr %498[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%500 = llvm.load %499 : !llvm.ptr -> i32
%501 = arith.constant 0 : i32
%502 = arith.extsi %501 : i32 to i64
%503 = llvm.getelementptr %arg0[%502] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%504 = llvm.getelementptr %503[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %500, %504 : i32, !llvm.ptr
%505 = llvm.load %456 : !llvm.ptr -> i64
%506 = llvm.getelementptr %arg0[%505] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%507 = llvm.getelementptr %506[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %473, %507 : i32, !llvm.ptr
%508 = llvm.load %456 : !llvm.ptr -> i64
%509 = llvm.getelementptr %arg0[%508] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%510 = llvm.getelementptr %509[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %482, %510 : i32, !llvm.ptr
%512 = arith.constant 0 : i32
%513 = llvm.load %456 : !llvm.ptr -> i64
%514 = arith.extsi %512 : i32 to i64
func.call @sift_down_pairs(%arg0, %514, %513) : (!llvm.ptr, i64, i64) -> ()
cf.br ^bb84
^bb86:
func.return
}
func.func @solve_mod(%arg0: i64) -> i64 {
%516 = arith.constant 32 : i32
%517 = arith.constant 4 : i32
%518 = arith.muli %516, %517 : i32
%519 = arith.constant 8 : i32
%520 = arith.extsi %518 : i32 to i64
%521 = arith.extsi %519 : i32 to i64
%515 = func.call @calloc(%520, %521) : (i64, i64) -> !llvm.ptr
%523 = arith.constant 32 : i32
%524 = arith.constant 4 : i32
%525 = arith.extsi %523 : i32 to i64
%526 = arith.extsi %524 : i32 to i64
%522 = func.call @calloc(%525, %526) : (i64, i64) -> !llvm.ptr
%527 = arith.constant 0 : i32
%528 = arith.constant 32 : i32
%529 = arith.index_cast %527 : i32 to index
%530 = arith.index_cast %528 : i32 to index
%532 = arith.constant 1 : index
%533 = arith.constant -1 : index
%534 = arith.cmpi sle, %529, %530 : index
%531 = arith.select %534, %532, %533 : index
cf.br ^bb87(%529 : index)
^bb87(%535: index):
%536 = arith.cmpi slt, %535, %530 : index
%537 = arith.cmpi sgt, %535, %530 : index
%538 = arith.select %534, %536, %537 : i1
cf.cond_br %538, ^bb88(%535 : index), ^bb89(%535 : index)
^bb88(%539: index):
%541 = arith.constant 4 : i32
%542 = arith.constant 8 : i32
%543 = arith.extsi %541 : i32 to i64
%544 = arith.extsi %542 : i32 to i64
%540 = func.call @calloc(%543, %544) : (i64, i64) -> !llvm.ptr
%545 = arith.constant 0 : i32
%546 = arith.constant 0 : i32
%547 = arith.constant 5 : i32
%548 = arith.index_cast %546 : i32 to index
%549 = arith.index_cast %547 : i32 to index
%551 = arith.constant 1 : index
%552 = arith.constant -1 : index
%553 = arith.cmpi sle, %548, %549 : index
%550 = arith.select %553, %551, %552 : index
cf.br ^bb90(%548, %545 : index, i32)
^bb90(%554: index, %555: i32):
%556 = arith.cmpi slt, %554, %549 : index
%557 = arith.cmpi sgt, %554, %549 : index
%558 = arith.select %553, %556, %557 : i1
cf.cond_br %558, ^bb91(%554, %555 : index, i32), ^bb92(%554, %555 : index, i32)
^bb91(%559: index, %560: i32):
%561 = arith.constant 1 : i32
%563 = arith.index_cast %559 : index to i32
%562 = arith.shli %561, %563 : i32
%565 = arith.index_cast %539 : index to i32
%564 = arith.andi %565, %562 : i32
%566 = arith.constant 0 : i32
%567 = arith.cmpi ne, %564, %566 : i32
%568 = scf.if %567 -> (i32) {
%569 = arith.constant 1 : i32
%570 = arith.addi %560, %569 : i32
%571 = arith.constant 4 : i32
%573 = arith.index_cast %559 : index to i32
%572 = arith.cmpi slt, %573, %571 : i32
cf.cond_br %572, ^bb93, ^bb94
^bb93:
%575 = arith.index_cast %559 : index to i64
%576 = llvm.getelementptr %540[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%574 = llvm.load %576 : !llvm.ptr -> i64
%577 = arith.constant 1 : i32
%579 = arith.extsi %577 : i32 to i64
%578 = arith.addi %574, %579 : i64
%580 = arith.index_cast %559 : index to i64
%581 = llvm.getelementptr %540[%580] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %578, %581 : i64, !llvm.ptr
cf.br ^bb95
^bb94:
%582 = arith.constant 0 : i32
%583 = arith.constant 4 : i32
%584 = arith.index_cast %582 : i32 to index
%585 = arith.index_cast %583 : i32 to index
%587 = arith.constant 1 : index
%588 = arith.constant -1 : index
%589 = arith.cmpi sle, %584, %585 : index
%586 = arith.select %589, %587, %588 : index
cf.br ^bb96(%584 : index)
^bb96(%590: index):
%591 = arith.cmpi slt, %590, %585 : index
%592 = arith.cmpi sgt, %590, %585 : index
%593 = arith.select %589, %591, %592 : i1
cf.cond_br %593, ^bb97(%590 : index), ^bb98(%590 : index)
^bb97(%594: index):
%596 = arith.index_cast %594 : index to i64
%597 = llvm.getelementptr %540[%596] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%595 = llvm.load %597 : !llvm.ptr -> i64
%598 = arith.constant 1 : i32
%600 = arith.extsi %598 : i32 to i64
%599 = arith.subi %595, %600 : i64
%601 = arith.index_cast %594 : index to i64
%602 = llvm.getelementptr %540[%601] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %599, %602 : i64, !llvm.ptr
%603 = arith.addi %594, %586 : index
cf.br ^bb96(%603 : index)
^bb98(%604: index):
cf.br ^bb95
^bb95:
scf.yield %570 : i32
} else {
scf.yield %560 : i32
}
%605 = arith.addi %559, %550 : index
cf.br ^bb90(%605, %568 : index, i32)
^bb92(%606: index, %607: i32):
%608 = arith.constant 0 : i32
%609 = arith.constant 4 : i32
%610 = arith.index_cast %608 : i32 to index
%611 = arith.index_cast %609 : i32 to index
%613 = arith.constant 1 : index
%614 = arith.constant -1 : index
%615 = arith.cmpi sle, %610, %611 : index
%612 = arith.select %615, %613, %614 : index
cf.br ^bb99(%610 : index)
^bb99(%616: index):
%617 = arith.cmpi slt, %616, %611 : index
%618 = arith.cmpi sgt, %616, %611 : index
%619 = arith.select %615, %617, %618 : i1
cf.cond_br %619, ^bb100(%616 : index), ^bb101(%616 : index)
^bb100(%620: index):
%622 = arith.index_cast %620 : index to i64
%623 = llvm.getelementptr %540[%622] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%621 = llvm.load %623 : !llvm.ptr -> i64
%624 = arith.constant 4 : i32
%626 = arith.index_cast %539 : index to i32
%625 = arith.muli %626, %624 : i32
%628 = arith.index_cast %620 : index to i32
%627 = arith.addi %625, %628 : i32
%629 = arith.extsi %627 : i32 to i64
%630 = llvm.getelementptr %515[%629] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %621, %630 : i64, !llvm.ptr
%631 = arith.addi %620, %612 : index
cf.br ^bb99(%631 : index)
^bb101(%632: index):
%633 = arith.index_cast %539 : index to i64
%634 = llvm.getelementptr %522[%633] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %607, %634 : i32, !llvm.ptr
func.call @free(%540) : (!llvm.ptr) -> ()
%636 = arith.addi %539, %531 : index
cf.br ^bb87(%636 : index)
^bb89(%637: index):
%639 = arith.constant 1024 : i32
%640 = arith.constant 8 : i32
%641 = arith.extsi %639 : i32 to i64
%642 = arith.extsi %640 : i32 to i64
%638 = func.call @calloc(%641, %642) : (i64, i64) -> !llvm.ptr
%643 = arith.constant 0 : i32
%644 = arith.constant 0 : i32
%645 = arith.constant 32 : i32
%646 = arith.index_cast %644 : i32 to index
%647 = arith.index_cast %645 : i32 to index
%649 = arith.constant 1 : index
%650 = arith.constant -1 : index
%651 = arith.cmpi sle, %646, %647 : index
%648 = arith.select %651, %649, %650 : index
cf.br ^bb102(%646, %643 : index, i32)
^bb102(%652: index, %653: i32):
%654 = arith.cmpi slt, %652, %647 : index
%655 = arith.cmpi sgt, %652, %647 : index
%656 = arith.select %651, %654, %655 : i1
cf.cond_br %656, ^bb103(%652, %653 : index, i32), ^bb104(%652, %653 : index, i32)
^bb103(%657: index, %658: i32):
%659 = arith.constant 0 : i32
%660 = arith.constant 32 : i32
%661 = arith.index_cast %659 : i32 to index
%662 = arith.index_cast %660 : i32 to index
%664 = arith.constant 1 : index
%665 = arith.constant -1 : index
%666 = arith.cmpi sle, %661, %662 : index
%663 = arith.select %666, %664, %665 : index
cf.br ^bb105(%661, %658 : index, i32)
^bb105(%667: index, %668: i32):
%669 = arith.cmpi slt, %667, %662 : index
%670 = arith.cmpi sgt, %667, %662 : index
%671 = arith.select %666, %669, %670 : i1
cf.cond_br %671, ^bb106(%667, %668 : index, i32), ^bb107(%667, %668 : index, i32)
^bb106(%672: index, %673: i32):
%675 = arith.constant 4 : i32
%677 = arith.index_cast %657 : index to i32
%676 = arith.muli %677, %675 : i32
%678 = arith.extsi %676 : i32 to i64
%679 = llvm.getelementptr %515[%678] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%674 = llvm.load %679 : !llvm.ptr -> i64
%681 = arith.constant 4 : i32
%683 = arith.index_cast %672 : index to i32
%682 = arith.muli %683, %681 : i32
%684 = arith.extsi %682 : i32 to i64
%685 = llvm.getelementptr %515[%684] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%680 = llvm.load %685 : !llvm.ptr -> i64
%686 = arith.subi %674, %680 : i64
%687 = arith.trunci %686 : i64 to i32
%688 = arith.constant 10 : i32
%689 = arith.addi %687, %688 : i32
%691 = arith.constant 4 : i32
%693 = arith.index_cast %657 : index to i32
%692 = arith.muli %693, %691 : i32
%694 = arith.constant 1 : i32
%695 = arith.addi %692, %694 : i32
%696 = arith.extsi %695 : i32 to i64
%697 = llvm.getelementptr %515[%696] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%690 = llvm.load %697 : !llvm.ptr -> i64
%699 = arith.constant 4 : i32
%701 = arith.index_cast %672 : index to i32
%700 = arith.muli %701, %699 : i32
%702 = arith.constant 1 : i32
%703 = arith.addi %700, %702 : i32
%704 = arith.extsi %703 : i32 to i64
%705 = llvm.getelementptr %515[%704] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%698 = llvm.load %705 : !llvm.ptr -> i64
%706 = arith.subi %690, %698 : i64
%707 = arith.trunci %706 : i64 to i32
%708 = arith.constant 10 : i32
%709 = arith.addi %707, %708 : i32
%711 = arith.constant 4 : i32
%713 = arith.index_cast %657 : index to i32
%712 = arith.muli %713, %711 : i32
%714 = arith.constant 2 : i32
%715 = arith.addi %712, %714 : i32
%716 = arith.extsi %715 : i32 to i64
%717 = llvm.getelementptr %515[%716] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%710 = llvm.load %717 : !llvm.ptr -> i64
%719 = arith.constant 4 : i32
%721 = arith.index_cast %672 : index to i32
%720 = arith.muli %721, %719 : i32
%722 = arith.constant 2 : i32
%723 = arith.addi %720, %722 : i32
%724 = arith.extsi %723 : i32 to i64
%725 = llvm.getelementptr %515[%724] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%718 = llvm.load %725 : !llvm.ptr -> i64
%726 = arith.subi %710, %718 : i64
%727 = arith.trunci %726 : i64 to i32
%728 = arith.constant 10 : i32
%729 = arith.addi %727, %728 : i32
%731 = arith.constant 4 : i32
%733 = arith.index_cast %657 : index to i32
%732 = arith.muli %733, %731 : i32
%734 = arith.constant 3 : i32
%735 = arith.addi %732, %734 : i32
%736 = arith.extsi %735 : i32 to i64
%737 = llvm.getelementptr %515[%736] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%730 = llvm.load %737 : !llvm.ptr -> i64
%739 = arith.constant 4 : i32
%741 = arith.index_cast %672 : index to i32
%740 = arith.muli %741, %739 : i32
%742 = arith.constant 3 : i32
%743 = arith.addi %740, %742 : i32
%744 = arith.extsi %743 : i32 to i64
%745 = llvm.getelementptr %515[%744] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%738 = llvm.load %745 : !llvm.ptr -> i64
%746 = arith.subi %730, %738 : i64
%747 = arith.trunci %746 : i64 to i32
%748 = arith.constant 10 : i32
%749 = arith.addi %747, %748 : i32
%750 = arith.constant 21 : i32
%751 = arith.muli %750, %709 : i32
%752 = arith.addi %689, %751 : i32
%753 = arith.constant 441 : i32
%754 = arith.muli %753, %729 : i32
%755 = arith.addi %752, %754 : i32
%756 = arith.constant 9261 : i32
%757 = arith.muli %756, %749 : i32
%758 = arith.addi %755, %757 : i32
%759 = arith.extsi %673 : i32 to i64
%760 = llvm.getelementptr %638[%759] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%761 = llvm.getelementptr %760[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %758, %761 : i32, !llvm.ptr
%763 = arith.index_cast %657 : index to i64
%764 = llvm.getelementptr %522[%763] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%762 = llvm.load %764 : !llvm.ptr -> i32
%766 = arith.index_cast %672 : index to i64
%767 = llvm.getelementptr %522[%766] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%765 = llvm.load %767 : !llvm.ptr -> i32
%768 = arith.addi %762, %765 : i32
%769 = arith.extsi %673 : i32 to i64
%770 = llvm.getelementptr %638[%769] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%771 = llvm.getelementptr %770[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
llvm.store %768, %771 : i32, !llvm.ptr
%772 = arith.constant 1 : i32
%773 = arith.addi %673, %772 : i32
%774 = arith.addi %672, %663 : index
cf.br ^bb105(%774, %773 : index, i32)
^bb107(%775: index, %776: i32):
%777 = arith.addi %657, %648 : index
cf.br ^bb102(%777, %776 : index, i32)
^bb104(%778: index, %779: i32):
%781 = arith.extsi %779 : i32 to i64
func.call @heapsort_pairs(%638, %781) : (!llvm.ptr, i64) -> ()
%783 = llvm.mlir.addressof @N : !llvm.ptr
%784 = llvm.load %783 : !llvm.ptr -> i32
%785 = arith.extsi %784 : i32 to i64
%786 = arith.constant 8 : i32
%787 = arith.extsi %786 : i32 to i64
%782 = func.call @calloc(%785, %787) : (i64, i64) -> !llvm.ptr
%788 = arith.constant 0 : i32
%789 = llvm.mlir.constant(1 : i64) : i64
%790 = llvm.alloca %789 x i32 : (i64) -> !llvm.ptr
llvm.store %788, %790 : i32, !llvm.ptr
cf.br ^bb108
^bb108:
%791 = llvm.load %790 : !llvm.ptr -> i32
%792 = arith.cmpi slt, %791, %779 : i32
cf.cond_br %792, ^bb109, ^bb110
^bb109:
%794 = llvm.load %790 : !llvm.ptr -> i32
%795 = arith.extsi %794 : i32 to i64
%796 = llvm.getelementptr %638[%795] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%793 = llvm.load %796 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%797 = llvm.load %790 : !llvm.ptr -> i32
%798 = arith.extsi %797 : i32 to i64
%799 = llvm.getelementptr %638[%798] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%800 = llvm.getelementptr %799[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%801 = llvm.load %800 : !llvm.ptr -> i32
%803 = llvm.mlir.addressof @N : !llvm.ptr
%804 = llvm.load %803 : !llvm.ptr -> i32
%805 = arith.extsi %804 : i32 to i64
%806 = arith.constant 8 : i32
%807 = arith.extsi %806 : i32 to i64
%802 = func.call @calloc(%805, %807) : (i64, i64) -> !llvm.ptr
cf.br ^bb111
^bb111:
%808 = llvm.load %790 : !llvm.ptr -> i32
%809 = arith.cmpi slt, %808, %779 : i32
%810 = scf.if %809 -> (i1) {
%812 = llvm.load %790 : !llvm.ptr -> i32
%813 = arith.extsi %812 : i32 to i64
%814 = llvm.getelementptr %638[%813] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%811 = llvm.load %814 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%815 = llvm.load %790 : !llvm.ptr -> i32
%816 = arith.extsi %815 : i32 to i64
%817 = llvm.getelementptr %638[%816] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%818 = llvm.getelementptr %817[0, 0] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%819 = llvm.load %818 : !llvm.ptr -> i32
%820 = arith.cmpi eq, %819, %801 : i32
scf.yield %820 : i1
} else {
%821 = arith.constant false
scf.yield %821 : i1
}
cf.cond_br %810, ^bb112, ^bb113
^bb112:
%823 = llvm.load %790 : !llvm.ptr -> i32
%824 = arith.extsi %823 : i32 to i64
%825 = llvm.getelementptr %638[%824] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%822 = llvm.load %825 : !llvm.ptr -> !llvm.struct<(i32, i32)>
%826 = llvm.load %790 : !llvm.ptr -> i32
%827 = arith.extsi %826 : i32 to i64
%828 = llvm.getelementptr %638[%827] : (!llvm.ptr, i64) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%829 = llvm.getelementptr %828[0, 1] : (!llvm.ptr) -> !llvm.ptr, !llvm.struct<(i32, i32)>
%830 = llvm.load %829 : !llvm.ptr -> i32
%831 = llvm.mlir.addressof @M : !llvm.ptr
%832 = llvm.load %831 : !llvm.ptr -> i32
%833 = arith.cmpi sle, %830, %832 : i32
cf.cond_br %833, ^bb114, ^bb115
^bb114:
%836 = arith.extsi %830 : i32 to i64
%837 = llvm.getelementptr %802[%836] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%835 = llvm.load %837 : !llvm.ptr -> i64
%838 = arith.constant 1 : i32
%839 = arith.extsi %838 : i32 to i64
%834 = func.call @madd(%835, %839, %arg0) : (i64, i64, i64) -> i64
%840 = arith.extsi %830 : i32 to i64
%841 = llvm.getelementptr %802[%840] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %834, %841 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%842 = llvm.load %790 : !llvm.ptr -> i32
%843 = arith.constant 1 : i32
%844 = arith.addi %842, %843 : i32
llvm.store %844, %790 : i32, !llvm.ptr
cf.br ^bb111
^bb113:
%846 = llvm.mlir.addressof @N : !llvm.ptr
%847 = llvm.load %846 : !llvm.ptr -> i32
%848 = arith.extsi %847 : i32 to i64
%849 = arith.constant 8 : i32
%850 = arith.extsi %849 : i32 to i64
%845 = func.call @calloc(%848, %850) : (i64, i64) -> !llvm.ptr
%852 = llvm.mlir.addressof @N : !llvm.ptr
%853 = llvm.load %852 : !llvm.ptr -> i32
%854 = arith.extsi %853 : i32 to i64
%855 = arith.constant 8 : i32
%856 = arith.extsi %855 : i32 to i64
%851 = func.call @calloc(%854, %856) : (i64, i64) -> !llvm.ptr
func.call @polymul(%845, %802, %802, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
func.call @polymul(%851, %845, %802, %arg0) : (!llvm.ptr, !llvm.ptr, !llvm.ptr, i64) -> ()
%859 = arith.constant 0 : i32
%860 = llvm.mlir.addressof @N : !llvm.ptr
%861 = llvm.load %860 : !llvm.ptr -> i32
%862 = arith.index_cast %859 : i32 to index
%863 = arith.index_cast %861 : i32 to index
%865 = arith.constant 1 : index
%866 = arith.constant -1 : index
%867 = arith.cmpi sle, %862, %863 : index
%864 = arith.select %867, %865, %866 : index
cf.br ^bb117(%862 : index)
^bb117(%868: index):
%869 = arith.cmpi slt, %868, %863 : index
%870 = arith.cmpi sgt, %868, %863 : index
%871 = arith.select %867, %869, %870 : i1
cf.cond_br %871, ^bb118(%868 : index), ^bb119(%868 : index)
^bb118(%872: index):
%875 = arith.index_cast %872 : index to i64
%876 = llvm.getelementptr %782[%875] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%874 = llvm.load %876 : !llvm.ptr -> i64
%878 = arith.index_cast %872 : index to i64
%879 = llvm.getelementptr %851[%878] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%877 = llvm.load %879 : !llvm.ptr -> i64
%873 = func.call @madd(%874, %877, %arg0) : (i64, i64, i64) -> i64
%880 = arith.index_cast %872 : index to i64
%881 = llvm.getelementptr %782[%880] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %873, %881 : i64, !llvm.ptr
%882 = arith.addi %872, %864 : index
cf.br ^bb117(%882 : index)
^bb119(%883: index):
func.call @free(%802) : (!llvm.ptr) -> ()
func.call @free(%845) : (!llvm.ptr) -> ()
func.call @free(%851) : (!llvm.ptr) -> ()
cf.br ^bb108
^bb110:
%888 = llvm.mlir.addressof @N : !llvm.ptr
%889 = llvm.load %888 : !llvm.ptr -> i32
%890 = arith.extsi %889 : i32 to i64
%891 = arith.constant 8 : i32
%892 = arith.extsi %891 : i32 to i64
%887 = func.call @calloc(%890, %892) : (i64, i64) -> !llvm.ptr
%894 = arith.constant 12 : i32
func.call @polypow(%887, %782, %894, %arg0) : (!llvm.ptr, !llvm.ptr, i32, i64) -> ()
%896 = llvm.mlir.addressof @M : !llvm.ptr
%897 = llvm.load %896 : !llvm.ptr -> i32
%898 = arith.extsi %897 : i32 to i64
%899 = llvm.getelementptr %887[%898] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%895 = llvm.load %899 : !llvm.ptr -> i64
func.call @free(%887) : (!llvm.ptr) -> ()
func.call @free(%782) : (!llvm.ptr) -> ()
func.call @free(%638) : (!llvm.ptr) -> ()
func.call @free(%515) : (!llvm.ptr) -> ()
func.call @free(%522) : (!llvm.ptr) -> ()
func.return %895 : i64
}
func.func @crt3(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%906 = llvm.mlir.addressof @P1 : !llvm.ptr
%907 = llvm.load %906 : !llvm.ptr -> i64
%908 = llvm.mlir.addressof @P2 : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> i64
%910 = arith.remsi %907, %909 : i64
%911 = llvm.mlir.addressof @P2 : !llvm.ptr
%912 = llvm.load %911 : !llvm.ptr -> i64
%905 = func.call @minv(%910, %912) : (i64, i64) -> i64
%913 = llvm.mlir.addressof @P1 : !llvm.ptr
%914 = llvm.load %913 : !llvm.ptr -> i64
%915 = arith.extsi %914 : i64 to i128
%916 = llvm.mlir.addressof @P2 : !llvm.ptr
%917 = llvm.load %916 : !llvm.ptr -> i64
%918 = arith.extsi %917 : i64 to i128
%920 = arith.trunci %915 : i128 to i64
%921 = arith.trunci %918 : i128 to i64
%919 = arith.muli %920, %921 : i64
%922 = arith.extsi %919 : i64 to i128
%924 = llvm.mlir.addressof @P2 : !llvm.ptr
%925 = llvm.load %924 : !llvm.ptr -> i64
%926 = arith.remsi %arg0, %925 : i64
%927 = llvm.mlir.addressof @P2 : !llvm.ptr
%928 = llvm.load %927 : !llvm.ptr -> i64
%923 = func.call @msub(%arg1, %926, %928) : (i64, i64, i64) -> i64
%930 = llvm.mlir.addressof @P2 : !llvm.ptr
%931 = llvm.load %930 : !llvm.ptr -> i64
%929 = func.call @mmul(%923, %905, %931) : (i64, i64, i64) -> i64
%932 = arith.extsi %arg0 : i64 to i128
%933 = llvm.mlir.addressof @P1 : !llvm.ptr
%934 = llvm.load %933 : !llvm.ptr -> i64
%935 = arith.extsi %934 : i64 to i128
%936 = arith.extsi %929 : i64 to i128
%938 = arith.trunci %935 : i128 to i64
%939 = arith.trunci %936 : i128 to i64
%937 = arith.muli %938, %939 : i64
%941 = arith.trunci %932 : i128 to i64
%940 = arith.addi %941, %937 : i64
%942 = arith.extsi %940 : i64 to i128
%944 = llvm.mlir.addressof @P3 : !llvm.ptr
%945 = llvm.load %944 : !llvm.ptr -> i64
%947 = arith.trunci %922 : i128 to i64
%946 = arith.remsi %947, %945 : i64
%948 = llvm.mlir.addressof @P3 : !llvm.ptr
%949 = llvm.load %948 : !llvm.ptr -> i64
%943 = func.call @minv(%946, %949) : (i64, i64) -> i64
%951 = llvm.mlir.addressof @P3 : !llvm.ptr
%952 = llvm.load %951 : !llvm.ptr -> i64
%954 = arith.trunci %942 : i128 to i64
%953 = arith.remsi %954, %952 : i64
%955 = llvm.mlir.addressof @P3 : !llvm.ptr
%956 = llvm.load %955 : !llvm.ptr -> i64
%950 = func.call @msub(%arg2, %953, %956) : (i64, i64, i64) -> i64
%958 = llvm.mlir.addressof @P3 : !llvm.ptr
%959 = llvm.load %958 : !llvm.ptr -> i64
%957 = func.call @mmul(%950, %943, %959) : (i64, i64, i64) -> i64
%960 = arith.extsi %957 : i64 to i128
%962 = arith.trunci %922 : i128 to i64
%963 = arith.trunci %960 : i128 to i64
%961 = arith.muli %962, %963 : i64
%965 = arith.trunci %942 : i128 to i64
%964 = arith.addi %965, %961 : i64
%966 = arith.extsi %964 : i64 to i128
%967 = arith.trunci %966 : i128 to i64
func.return %967 : i64
}
func.func @main() -> i32 {
%969 = llvm.mlir.addressof @P1 : !llvm.ptr
%970 = llvm.load %969 : !llvm.ptr -> i64
%968 = func.call @solve_mod(%970) : (i64) -> i64
%972 = llvm.mlir.addressof @P2 : !llvm.ptr
%973 = llvm.load %972 : !llvm.ptr -> i64
%971 = func.call @solve_mod(%973) : (i64) -> i64
%975 = llvm.mlir.addressof @P3 : !llvm.ptr
%976 = llvm.load %975 : !llvm.ptr -> i64
%974 = func.call @solve_mod(%976) : (i64) -> i64
%977 = llvm.mlir.addressof @str_0 : !llvm.ptr
%978 = func.call @crt3(%968, %971, %974) : (i64, i64, i64) -> i64
%979 = llvm.call @printf(%977, %978) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%980 = arith.constant 0 : i32
func.return %980 : i32
}
}