← All problems Problem 624
Two Heads: Q(P(10^18), 1000000009) via matrix geometric series mod p.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)?Space complexity O(1)?Approach Flow solution Not curated Verdict Unknown
Flow source
# Project Euler 624
# Two Heads: Q(P(10^18), 1000000009) via matrix geometric series mod p.
const P: i64 = 1000000009
function modpow(base0: i64, exp0: i64, mod: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = base0 % mod
let mut e: i64 = exp0
while e > 0 {
if (e & 1) == 1 {
let t: i128 = (r as i128) * (b as i128) % (mod as i128)
r = t as i64
}
let t2: i128 = (b as i128) * (b as i128) % (mod as i128)
b = t2 as i64
e = e / 2
}
return r
}
function main() -> i32 {
let n: i64 = 1000000000000000000
# B = A^n where A = [[1,1],[1,0]]
let mut a00: i64 = 1
let mut a01: i64 = 1
let mut a10: i64 = 1
let mut a11: i64 = 0
let mut r00: i64 = 1
let mut r01: i64 = 0
let mut r10: i64 = 0
let mut r11: i64 = 1
let mut e: i64 = n
while e > 0 {
if (e & 1) == 1 {
let n00: i64 = (r00 * a00 + r01 * a10) % P
let n01: i64 = (r00 * a01 + r01 * a11) % P
let n10: i64 = (r10 * a00 + r11 * a10) % P
let n11: i64 = (r10 * a01 + r11 * a11) % P
r00 = n00; r01 = n01; r10 = n10; r11 = n11
}
let b00: i64 = (a00 * a00 + a01 * a10) % P
let b01: i64 = (a00 * a01 + a01 * a11) % P
let b10: i64 = (a10 * a00 + a11 * a10) % P
let b11: i64 = (a10 * a01 + a11 * a11) % P
a00 = b00; a01 = b01; a10 = b10; a11 = b11
e = e / 2
}
let inv2: i64 = (P + 1) / 2
let s: i64 = modpow(inv2, n, P)
let m00: i64 = r00 * s % P
let m01: i64 = r01 * s % P
let m10: i64 = r10 * s % P
let m11: i64 = r11 * s % P
let i00: i64 = (1 - m00 + P) % P
let i01: i64 = (0 - m01 + P) % P
let i10: i64 = (0 - m10 + P) % P
let i11: i64 = (1 - m11 + P) % P
let mut det: i64 = (i00 * i11 - i01 * i10) % P
if det < 0 { det = det + P }
let inv_det: i64 = modpow(det, P - 2, P)
# inv = [[i11, -i01], [-i10, i00]] * inv_det
let inv00: i64 = i11 * inv_det % P
let inv01: i64 = ((0 - i01 + P) % P) * inv_det % P
let inv10: i64 = ((0 - i10 + P) % P) * inv_det % P
let inv11: i64 = i00 * inv_det % P
# w = inv * [0,1]
let w0: i64 = inv01
let w1: i64 = inv11
# x = M * w
let x1: i64 = (m10 * w0 + m11 * w1) % P
let mut q: i64 = x1 % P
if q == 0 { q = P }
printf("%lld\n", q)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod);
int32_t main(void);
static const int64_t P = 1000000009;
int64_t modpow_i64_i64_i64(int64_t base0, int64_t exp0, int64_t mod) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((base0), (mod));
int64_t e = exp0;
while (e > 0) {
if ((e & 1) == 1) {
__int128 t = FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(b)))), (((__int128)(mod))));
r = ((int64_t)(t));
}
__int128 t2 = FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(mod))));
b = ((int64_t)(t2));
e = FLOW_CHECKED_DIV((e), (2));
}
return r;
}
int32_t main(void) {
int64_t n = 1000000000000000000;
int64_t a00 = 1;
int64_t a01 = 1;
int64_t a10 = 1;
int64_t a11 = 0;
int64_t r00 = 1;
int64_t r01 = 0;
int64_t r10 = 0;
int64_t r11 = 1;
int64_t e = n;
while (e > 0) {
if ((e & 1) == 1) {
int64_t n00 = FLOW_CHECKED_MOD((((r00 * a00) + (r01 * a10))), (P));
int64_t n01 = FLOW_CHECKED_MOD((((r00 * a01) + (r01 * a11))), (P));
int64_t n10 = FLOW_CHECKED_MOD((((r10 * a00) + (r11 * a10))), (P));
int64_t n11 = FLOW_CHECKED_MOD((((r10 * a01) + (r11 * a11))), (P));
r00 = n00;
r01 = n01;
r10 = n10;
r11 = n11;
}
int64_t b00 = FLOW_CHECKED_MOD((((a00 * a00) + (a01 * a10))), (P));
int64_t b01 = FLOW_CHECKED_MOD((((a00 * a01) + (a01 * a11))), (P));
int64_t b10 = FLOW_CHECKED_MOD((((a10 * a00) + (a11 * a10))), (P));
int64_t b11 = FLOW_CHECKED_MOD((((a10 * a01) + (a11 * a11))), (P));
a00 = b00;
a01 = b01;
a10 = b10;
a11 = b11;
e = FLOW_CHECKED_DIV((e), (2));
}
int64_t inv2 = FLOW_CHECKED_DIV(((P + 1)), (2));
int64_t s = modpow_i64_i64_i64(inv2, n, P);
int64_t m00 = FLOW_CHECKED_MOD(((r00 * s)), (P));
int64_t m01 = FLOW_CHECKED_MOD(((r01 * s)), (P));
int64_t m10 = FLOW_CHECKED_MOD(((r10 * s)), (P));
int64_t m11 = FLOW_CHECKED_MOD(((r11 * s)), (P));
int64_t i00 = FLOW_CHECKED_MOD((((1 - m00) + P)), (P));
int64_t i01 = FLOW_CHECKED_MOD((((0 - m01) + P)), (P));
int64_t i10 = FLOW_CHECKED_MOD((((0 - m10) + P)), (P));
int64_t i11 = FLOW_CHECKED_MOD((((1 - m11) + P)), (P));
int64_t det = FLOW_CHECKED_MOD((((i00 * i11) - (i01 * i10))), (P));
if (det < 0) {
det = (det + P);
}
int64_t inv_det = modpow_i64_i64_i64(det, (P - 2), P);
int64_t inv00 = FLOW_CHECKED_MOD(((i11 * inv_det)), (P));
int64_t inv01 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((0 - i01) + P)), (P)) * inv_det)), (P));
int64_t inv10 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((0 - i10) + P)), (P)) * inv_det)), (P));
int64_t inv11 = FLOW_CHECKED_MOD(((i00 * inv_det)), (P));
int64_t w0 = inv01;
int64_t w1 = inv11;
int64_t x1 = FLOW_CHECKED_MOD((((m10 * w0) + (m11 * w1))), (P));
int64_t q = FLOW_CHECKED_MOD((x1), (P));
if (q == 0) {
q = P;
}
printf("%lld\n", q);
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>
// Constant: P
llvm.mlir.global internal constant @P(1000000009 : i64) : i64
func.func @modpow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%0 = arith.constant 1 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.remsi %arg0, %arg2 : i64
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i64, !llvm.ptr
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%9 = llvm.load %8 : !llvm.ptr -> i64
%10 = arith.constant 0 : i32
%12 = arith.extsi %10 : i32 to i64
%11 = arith.cmpi sgt, %9, %12 : i64
cf.cond_br %11, ^bb1, ^bb2
^bb1:
%13 = llvm.load %8 : !llvm.ptr -> i64
%14 = arith.constant 1 : i32
%16 = arith.extsi %14 : i32 to i64
%15 = arith.andi %13, %16 : i64
%17 = arith.constant 1 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.cmpi eq, %15, %19 : i64
cf.cond_br %18, ^bb3, ^bb4
^bb3:
%20 = llvm.load %3 : !llvm.ptr -> i64
%21 = arith.extsi %20 : i64 to i128
%22 = llvm.load %6 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%25 = arith.trunci %21 : i128 to i64
%26 = arith.trunci %23 : i128 to i64
%24 = arith.muli %25, %26 : i64
%27 = arith.extsi %arg2 : i64 to i128
%29 = arith.trunci %27 : i128 to i64
%28 = arith.remsi %24, %29 : i64
%30 = arith.extsi %28 : i64 to i128
%31 = arith.trunci %30 : i128 to i64
llvm.store %31, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%32 = llvm.load %6 : !llvm.ptr -> i64
%33 = arith.extsi %32 : i64 to i128
%34 = llvm.load %6 : !llvm.ptr -> i64
%35 = arith.extsi %34 : i64 to i128
%37 = arith.trunci %33 : i128 to i64
%38 = arith.trunci %35 : i128 to i64
%36 = arith.muli %37, %38 : i64
%39 = arith.extsi %arg2 : i64 to i128
%41 = arith.trunci %39 : i128 to i64
%40 = arith.remsi %36, %41 : i64
%42 = arith.extsi %40 : i64 to i128
%43 = arith.trunci %42 : i128 to i64
llvm.store %43, %6 : i64, !llvm.ptr
%44 = llvm.load %8 : !llvm.ptr -> i64
%45 = arith.constant 2 : i32
%47 = arith.extsi %45 : i32 to i64
%46 = arith.divsi %44, %47 : i64
llvm.store %46, %8 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%48 = llvm.load %3 : !llvm.ptr -> i64
func.return %48 : i64
}
func.func @main() -> i32 {
%49 = arith.constant 999999995705032704 : i32
%50 = arith.extsi %49 : i32 to i64
%51 = arith.constant 1 : i32
%52 = arith.extsi %51 : i32 to 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.constant 1 : i32
%56 = arith.extsi %55 : i32 to i64
%57 = llvm.mlir.constant(1 : i64) : i64
%58 = llvm.alloca %57 x i64 : (i64) -> !llvm.ptr
llvm.store %56, %58 : i64, !llvm.ptr
%59 = arith.constant 1 : i32
%60 = arith.extsi %59 : i32 to i64
%61 = llvm.mlir.constant(1 : i64) : i64
%62 = llvm.alloca %61 x i64 : (i64) -> !llvm.ptr
llvm.store %60, %62 : i64, !llvm.ptr
%63 = arith.constant 0 : i32
%64 = arith.extsi %63 : i32 to i64
%65 = llvm.mlir.constant(1 : i64) : i64
%66 = llvm.alloca %65 x i64 : (i64) -> !llvm.ptr
llvm.store %64, %66 : i64, !llvm.ptr
%67 = arith.constant 1 : i32
%68 = arith.extsi %67 : i32 to i64
%69 = llvm.mlir.constant(1 : i64) : i64
%70 = llvm.alloca %69 x i64 : (i64) -> !llvm.ptr
llvm.store %68, %70 : i64, !llvm.ptr
%71 = arith.constant 0 : i32
%72 = arith.extsi %71 : i32 to i64
%73 = llvm.mlir.constant(1 : i64) : i64
%74 = llvm.alloca %73 x i64 : (i64) -> !llvm.ptr
llvm.store %72, %74 : i64, !llvm.ptr
%75 = arith.constant 0 : i32
%76 = arith.extsi %75 : i32 to i64
%77 = llvm.mlir.constant(1 : i64) : i64
%78 = llvm.alloca %77 x i64 : (i64) -> !llvm.ptr
llvm.store %76, %78 : i64, !llvm.ptr
%79 = arith.constant 1 : i32
%80 = arith.extsi %79 : i32 to i64
%81 = llvm.mlir.constant(1 : i64) : i64
%82 = llvm.alloca %81 x i64 : (i64) -> !llvm.ptr
llvm.store %80, %82 : i64, !llvm.ptr
%83 = llvm.mlir.constant(1 : i64) : i64
%84 = llvm.alloca %83 x i64 : (i64) -> !llvm.ptr
llvm.store %50, %84 : i64, !llvm.ptr
cf.br ^bb6
^bb6:
%85 = llvm.load %84 : !llvm.ptr -> i64
%86 = arith.constant 0 : i32
%88 = arith.extsi %86 : i32 to i64
%87 = arith.cmpi sgt, %85, %88 : i64
cf.cond_br %87, ^bb7, ^bb8
^bb7:
%89 = llvm.load %84 : !llvm.ptr -> i64
%90 = arith.constant 1 : i32
%92 = arith.extsi %90 : i32 to i64
%91 = arith.andi %89, %92 : i64
%93 = arith.constant 1 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.cmpi eq, %91, %95 : i64
cf.cond_br %94, ^bb9, ^bb10
^bb9:
%96 = llvm.load %70 : !llvm.ptr -> i64
%97 = llvm.load %54 : !llvm.ptr -> i64
%98 = arith.muli %96, %97 : i64
%99 = llvm.load %74 : !llvm.ptr -> i64
%100 = llvm.load %62 : !llvm.ptr -> i64
%101 = arith.muli %99, %100 : i64
%102 = arith.addi %98, %101 : i64
%103 = llvm.mlir.addressof @P : !llvm.ptr
%104 = llvm.load %103 : !llvm.ptr -> i64
%105 = arith.remsi %102, %104 : i64
%106 = llvm.load %70 : !llvm.ptr -> i64
%107 = llvm.load %58 : !llvm.ptr -> i64
%108 = arith.muli %106, %107 : i64
%109 = llvm.load %74 : !llvm.ptr -> i64
%110 = llvm.load %66 : !llvm.ptr -> i64
%111 = arith.muli %109, %110 : i64
%112 = arith.addi %108, %111 : i64
%113 = llvm.mlir.addressof @P : !llvm.ptr
%114 = llvm.load %113 : !llvm.ptr -> i64
%115 = arith.remsi %112, %114 : i64
%116 = llvm.load %78 : !llvm.ptr -> i64
%117 = llvm.load %54 : !llvm.ptr -> i64
%118 = arith.muli %116, %117 : i64
%119 = llvm.load %82 : !llvm.ptr -> i64
%120 = llvm.load %62 : !llvm.ptr -> i64
%121 = arith.muli %119, %120 : i64
%122 = arith.addi %118, %121 : i64
%123 = llvm.mlir.addressof @P : !llvm.ptr
%124 = llvm.load %123 : !llvm.ptr -> i64
%125 = arith.remsi %122, %124 : i64
%126 = llvm.load %78 : !llvm.ptr -> i64
%127 = llvm.load %58 : !llvm.ptr -> i64
%128 = arith.muli %126, %127 : i64
%129 = llvm.load %82 : !llvm.ptr -> i64
%130 = llvm.load %66 : !llvm.ptr -> i64
%131 = arith.muli %129, %130 : i64
%132 = arith.addi %128, %131 : i64
%133 = llvm.mlir.addressof @P : !llvm.ptr
%134 = llvm.load %133 : !llvm.ptr -> i64
%135 = arith.remsi %132, %134 : i64
llvm.store %105, %70 : i64, !llvm.ptr
llvm.store %115, %74 : i64, !llvm.ptr
llvm.store %125, %78 : i64, !llvm.ptr
llvm.store %135, %82 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%136 = llvm.load %54 : !llvm.ptr -> i64
%137 = llvm.load %54 : !llvm.ptr -> i64
%138 = arith.muli %136, %137 : i64
%139 = llvm.load %58 : !llvm.ptr -> i64
%140 = llvm.load %62 : !llvm.ptr -> i64
%141 = arith.muli %139, %140 : i64
%142 = arith.addi %138, %141 : i64
%143 = llvm.mlir.addressof @P : !llvm.ptr
%144 = llvm.load %143 : !llvm.ptr -> i64
%145 = arith.remsi %142, %144 : i64
%146 = llvm.load %54 : !llvm.ptr -> i64
%147 = llvm.load %58 : !llvm.ptr -> i64
%148 = arith.muli %146, %147 : i64
%149 = llvm.load %58 : !llvm.ptr -> i64
%150 = llvm.load %66 : !llvm.ptr -> i64
%151 = arith.muli %149, %150 : i64
%152 = arith.addi %148, %151 : i64
%153 = llvm.mlir.addressof @P : !llvm.ptr
%154 = llvm.load %153 : !llvm.ptr -> i64
%155 = arith.remsi %152, %154 : i64
%156 = llvm.load %62 : !llvm.ptr -> i64
%157 = llvm.load %54 : !llvm.ptr -> i64
%158 = arith.muli %156, %157 : i64
%159 = llvm.load %66 : !llvm.ptr -> i64
%160 = llvm.load %62 : !llvm.ptr -> i64
%161 = arith.muli %159, %160 : i64
%162 = arith.addi %158, %161 : i64
%163 = llvm.mlir.addressof @P : !llvm.ptr
%164 = llvm.load %163 : !llvm.ptr -> i64
%165 = arith.remsi %162, %164 : i64
%166 = llvm.load %62 : !llvm.ptr -> i64
%167 = llvm.load %58 : !llvm.ptr -> i64
%168 = arith.muli %166, %167 : i64
%169 = llvm.load %66 : !llvm.ptr -> i64
%170 = llvm.load %66 : !llvm.ptr -> i64
%171 = arith.muli %169, %170 : i64
%172 = arith.addi %168, %171 : i64
%173 = llvm.mlir.addressof @P : !llvm.ptr
%174 = llvm.load %173 : !llvm.ptr -> i64
%175 = arith.remsi %172, %174 : i64
llvm.store %145, %54 : i64, !llvm.ptr
llvm.store %155, %58 : i64, !llvm.ptr
llvm.store %165, %62 : i64, !llvm.ptr
llvm.store %175, %66 : i64, !llvm.ptr
%176 = llvm.load %84 : !llvm.ptr -> i64
%177 = arith.constant 2 : i32
%179 = arith.extsi %177 : i32 to i64
%178 = arith.divsi %176, %179 : i64
llvm.store %178, %84 : i64, !llvm.ptr
cf.br ^bb6
^bb8:
%180 = llvm.mlir.addressof @P : !llvm.ptr
%181 = llvm.load %180 : !llvm.ptr -> i64
%182 = arith.constant 1 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.addi %181, %184 : i64
%185 = arith.constant 2 : i32
%187 = arith.extsi %185 : i32 to i64
%186 = arith.divsi %183, %187 : i64
%189 = llvm.mlir.addressof @P : !llvm.ptr
%190 = llvm.load %189 : !llvm.ptr -> i64
%188 = func.call @modpow(%186, %50, %190) : (i64, i64, i64) -> i64
%191 = llvm.load %70 : !llvm.ptr -> i64
%192 = arith.muli %191, %188 : i64
%193 = llvm.mlir.addressof @P : !llvm.ptr
%194 = llvm.load %193 : !llvm.ptr -> i64
%195 = arith.remsi %192, %194 : i64
%196 = llvm.load %74 : !llvm.ptr -> i64
%197 = arith.muli %196, %188 : i64
%198 = llvm.mlir.addressof @P : !llvm.ptr
%199 = llvm.load %198 : !llvm.ptr -> i64
%200 = arith.remsi %197, %199 : i64
%201 = llvm.load %78 : !llvm.ptr -> i64
%202 = arith.muli %201, %188 : i64
%203 = llvm.mlir.addressof @P : !llvm.ptr
%204 = llvm.load %203 : !llvm.ptr -> i64
%205 = arith.remsi %202, %204 : i64
%206 = llvm.load %82 : !llvm.ptr -> i64
%207 = arith.muli %206, %188 : i64
%208 = llvm.mlir.addressof @P : !llvm.ptr
%209 = llvm.load %208 : !llvm.ptr -> i64
%210 = arith.remsi %207, %209 : i64
%211 = arith.constant 1 : i32
%213 = arith.extsi %211 : i32 to i64
%212 = arith.subi %213, %195 : i64
%214 = llvm.mlir.addressof @P : !llvm.ptr
%215 = llvm.load %214 : !llvm.ptr -> i64
%216 = arith.addi %212, %215 : i64
%217 = llvm.mlir.addressof @P : !llvm.ptr
%218 = llvm.load %217 : !llvm.ptr -> i64
%219 = arith.remsi %216, %218 : i64
%220 = arith.constant 0 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.subi %222, %200 : i64
%223 = llvm.mlir.addressof @P : !llvm.ptr
%224 = llvm.load %223 : !llvm.ptr -> i64
%225 = arith.addi %221, %224 : i64
%226 = llvm.mlir.addressof @P : !llvm.ptr
%227 = llvm.load %226 : !llvm.ptr -> i64
%228 = arith.remsi %225, %227 : i64
%229 = arith.constant 0 : i32
%231 = arith.extsi %229 : i32 to i64
%230 = arith.subi %231, %205 : i64
%232 = llvm.mlir.addressof @P : !llvm.ptr
%233 = llvm.load %232 : !llvm.ptr -> i64
%234 = arith.addi %230, %233 : i64
%235 = llvm.mlir.addressof @P : !llvm.ptr
%236 = llvm.load %235 : !llvm.ptr -> i64
%237 = arith.remsi %234, %236 : i64
%238 = arith.constant 1 : i32
%240 = arith.extsi %238 : i32 to i64
%239 = arith.subi %240, %210 : i64
%241 = llvm.mlir.addressof @P : !llvm.ptr
%242 = llvm.load %241 : !llvm.ptr -> i64
%243 = arith.addi %239, %242 : i64
%244 = llvm.mlir.addressof @P : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> i64
%246 = arith.remsi %243, %245 : i64
%247 = arith.muli %219, %246 : i64
%248 = arith.muli %228, %237 : i64
%249 = arith.subi %247, %248 : i64
%250 = llvm.mlir.addressof @P : !llvm.ptr
%251 = llvm.load %250 : !llvm.ptr -> i64
%252 = arith.remsi %249, %251 : i64
%253 = llvm.mlir.constant(1 : i64) : i64
%254 = llvm.alloca %253 x i64 : (i64) -> !llvm.ptr
llvm.store %252, %254 : i64, !llvm.ptr
%255 = llvm.load %254 : !llvm.ptr -> i64
%256 = arith.constant 0 : i32
%258 = arith.extsi %256 : i32 to i64
%257 = arith.cmpi slt, %255, %258 : i64
cf.cond_br %257, ^bb12, ^bb13
^bb12:
%259 = llvm.load %254 : !llvm.ptr -> i64
%260 = llvm.mlir.addressof @P : !llvm.ptr
%261 = llvm.load %260 : !llvm.ptr -> i64
%262 = arith.addi %259, %261 : i64
llvm.store %262, %254 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
%264 = llvm.load %254 : !llvm.ptr -> i64
%265 = llvm.mlir.addressof @P : !llvm.ptr
%266 = llvm.load %265 : !llvm.ptr -> i64
%267 = arith.constant 2 : i32
%269 = arith.extsi %267 : i32 to i64
%268 = arith.subi %266, %269 : i64
%270 = llvm.mlir.addressof @P : !llvm.ptr
%271 = llvm.load %270 : !llvm.ptr -> i64
%263 = func.call @modpow(%264, %268, %271) : (i64, i64, i64) -> i64
%272 = arith.muli %246, %263 : i64
%273 = llvm.mlir.addressof @P : !llvm.ptr
%274 = llvm.load %273 : !llvm.ptr -> i64
%275 = arith.remsi %272, %274 : i64
%276 = arith.constant 0 : i32
%278 = arith.extsi %276 : i32 to i64
%277 = arith.subi %278, %228 : i64
%279 = llvm.mlir.addressof @P : !llvm.ptr
%280 = llvm.load %279 : !llvm.ptr -> i64
%281 = arith.addi %277, %280 : i64
%282 = llvm.mlir.addressof @P : !llvm.ptr
%283 = llvm.load %282 : !llvm.ptr -> i64
%284 = arith.remsi %281, %283 : i64
%285 = arith.muli %284, %263 : i64
%286 = llvm.mlir.addressof @P : !llvm.ptr
%287 = llvm.load %286 : !llvm.ptr -> i64
%288 = arith.remsi %285, %287 : i64
%289 = arith.constant 0 : i32
%291 = arith.extsi %289 : i32 to i64
%290 = arith.subi %291, %237 : i64
%292 = llvm.mlir.addressof @P : !llvm.ptr
%293 = llvm.load %292 : !llvm.ptr -> i64
%294 = arith.addi %290, %293 : i64
%295 = llvm.mlir.addressof @P : !llvm.ptr
%296 = llvm.load %295 : !llvm.ptr -> i64
%297 = arith.remsi %294, %296 : i64
%298 = arith.muli %297, %263 : i64
%299 = llvm.mlir.addressof @P : !llvm.ptr
%300 = llvm.load %299 : !llvm.ptr -> i64
%301 = arith.remsi %298, %300 : i64
%302 = arith.muli %219, %263 : i64
%303 = llvm.mlir.addressof @P : !llvm.ptr
%304 = llvm.load %303 : !llvm.ptr -> i64
%305 = arith.remsi %302, %304 : i64
%306 = arith.muli %205, %288 : i64
%307 = arith.muli %210, %305 : i64
%308 = arith.addi %306, %307 : i64
%309 = llvm.mlir.addressof @P : !llvm.ptr
%310 = llvm.load %309 : !llvm.ptr -> i64
%311 = arith.remsi %308, %310 : i64
%312 = llvm.mlir.addressof @P : !llvm.ptr
%313 = llvm.load %312 : !llvm.ptr -> i64
%314 = arith.remsi %311, %313 : i64
%315 = llvm.mlir.constant(1 : i64) : i64
%316 = llvm.alloca %315 x i64 : (i64) -> !llvm.ptr
llvm.store %314, %316 : i64, !llvm.ptr
%317 = llvm.load %316 : !llvm.ptr -> i64
%318 = arith.constant 0 : i32
%320 = arith.extsi %318 : i32 to i64
%319 = arith.cmpi eq, %317, %320 : i64
cf.cond_br %319, ^bb15, ^bb16
^bb15:
%321 = llvm.mlir.addressof @P : !llvm.ptr
%322 = llvm.load %321 : !llvm.ptr -> i64
llvm.store %322, %316 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%323 = llvm.mlir.addressof @str_0 : !llvm.ptr
%324 = llvm.load %316 : !llvm.ptr -> i64
%325 = llvm.call @printf(%323, %324) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%326 = arith.constant 0 : i32
func.return %326 : i32
}
}