Problem 322
T(10^18, 10^12-10): binomial coeffs divisible by 10.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n) | O(n^2) |
|---|
| Space complexity | O(n^2) | O(n) |
|---|
| Approach | Flow solution | Pascal triangle computation |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 322
# T(10^18, 10^12-10): binomial coeffs divisible by 10.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function digits_base(x0: i64, base: i64, out: ptr<i64>) -> i64 {
let mut x: i64 = x0
if x == 0 {
out[0] = 0
return 1
}
let mut n: i64 = 0
while x > 0 {
out[n] = x % base
x = x / base
n = n + 1
}
return n
}
function count_supermask_lt(limit: i64, mask: i64) -> i64 {
if limit <= 0 { return 0 }
let mut bits: i64 = 0
let mut t: i64 = limit
while t > 0 {
bits = bits + 1
t = t / 2
}
let mut dp_tight: i64 = 1
let mut dp_loose: i64 = 0
let mut p: i64 = bits - 1
while p >= 0 {
let lim_bit: i64 = (limit >> p) & 1
let forced: i64 = (mask >> p) & 1
let mut new_tight: i64 = 0
let mut new_loose: i64 = 0
if dp_loose != 0 {
if forced == 1 { new_loose = new_loose + dp_loose }
else { new_loose = new_loose + dp_loose * 2 }
}
if dp_tight != 0 {
if forced == 1 {
if lim_bit == 1 { new_tight = new_tight + dp_tight }
} else {
if lim_bit == 0 { new_tight = new_tight + dp_tight }
else {
new_loose = new_loose + dp_tight
new_tight = new_tight + dp_tight
}
}
}
dp_tight = new_tight
dp_loose = new_loose
p = p - 1
}
return dp_loose
}
function lucas_dp(pos: i64, tight: i64, L: i64, lim_msb: ptr<i64>, n_msb: ptr<i64>, base: i64, memo: ptr<i64>) -> i64 {
if pos == L { return 1 }
let key: i64 = pos * 2 + tight
if memo[key] >= 0 { return memo[key] }
let limd: i64 = lim_msb[pos]
let mind: i64 = n_msb[pos]
let mut maxd: i64 = base - 1
if tight == 1 { maxd = limd }
let mut total: i64 = 0
let mut d: i64 = mind
while d <= maxd {
let nt: i64 = 0
if tight == 1 && d == limd { nt = 1 }
total = total + lucas_dp(pos + 1, nt, L, lim_msb, n_msb, base, memo)
d = d + 1
}
memo[key] = total
return total
}
function count_lucas_not_div_lt(limit: i64, n: i64, base: i64) -> i64 {
if limit <= 0 { return 0 }
let upper: i64 = limit - 1
let lim_d: ptr<i64> = calloc(80, 8)
let n_d: ptr<i64> = calloc(80, 8)
let ld: i64 = digits_base(upper, base, lim_d)
let nd: i64 = digits_base(n, base, n_d)
let mut L: i64 = ld
if nd > L { L = nd }
let lim_msb: ptr<i64> = calloc(L, 8)
let n_msb: ptr<i64> = calloc(L, 8)
let mut i: i64 = 0
while i < L {
let li: i64 = 0
if L - 1 - i < ld { li = lim_d[L - 1 - i] }
let ni: i64 = 0
if L - 1 - i < nd { ni = n_d[L - 1 - i] }
lim_msb[i] = li
n_msb[i] = ni
i = i + 1
}
let memo: ptr<i64> = calloc(2 * L + 2, 8)
i = 0
while i < 2 * L + 2 {
memo[i] = -1
i = i + 1
}
let ans: i64 = lucas_dp(0, 1, L, lim_msb, n_msb, base, memo)
free(lim_d); free(n_d); free(lim_msb); free(n_msb); free(memo)
return ans
}
function mod_inverse_odd(a0: i64, mod: i64) -> i64 {
# mod is power of two; a odd. Use Hensel / binary extended.
let mut a: i64 = a0 % mod
let mut x: i64 = 1
# Newton: x <- x*(2-a*x) mod mod
let mut i: i64 = 0
while i < 6 {
let ax: i64 = (a * x) % mod
x = (x * ((2 - ax) % mod + mod) % mod) % mod
i = i + 1
}
return x % mod
}
function count_not_div10_lt(m: i64, n: i64) -> i64 {
if m <= 0 { return 0 }
let n_digits: ptr<i64> = calloc(40, 8)
let nd: i64 = digits_base(n, 5, n_digits)
# generate lows iteratively
let mut lows: ptr<i64> = calloc(1, 8)
lows[0] = 0
let mut lc: i64 = 1
let mut pow5: i64 = 1
let mut di: i64 = 0
while di < nd {
let dmin: i64 = n_digits[di]
let newc: i64 = lc * (5 - dmin)
let newlows: ptr<i64> = calloc(newc, 8)
let mut k: i64 = 0
let mut i: i64 = 0
while i < lc {
let mut d: i64 = dmin
while d < 5 {
newlows[k] = lows[i] + d * pow5
k = k + 1
d = d + 1
}
i = i + 1
}
free(lows)
lows = newlows
lc = newc
pow5 = pow5 * 5
di = di + 1
}
let B: i64 = pow5
let max_h: i64 = (m - 1) / B
let mut kk: i64 = 1
let mut tmp: i64 = max_h
while tmp > 0 {
kk = kk + 1
tmp = tmp / 2
}
if kk < 1 { kk = 1 }
let mod: i64 = 1 << kk
let invB: i64 = mod_inverse_odd(B % mod, mod)
let required_low: i64 = n & (mod - 1)
let free_pos: ptr<i64> = calloc(64, 8)
let mut fc: i64 = 0
let mut b: i64 = 0
while b < kk {
if ((required_low >> b) & 1) == 0 {
free_pos[fc] = b
fc = fc + 1
}
b = b + 1
}
let imods: ptr<i64> = calloc(1 << fc, 8)
let mut subset: i64 = 0
while subset < (1 << fc) {
let mut val: i64 = required_low
let mut j: i64 = 0
while j < fc {
if ((subset >> j) & 1) == 1 {
val = val | (1 << free_pos[j])
}
j = j + 1
}
imods[subset] = val
subset = subset + 1
}
let mut out: i64 = 0
let mut li: i64 = 0
while li < lc {
let low: i64 = lows[li]
if low < m {
let h_max: i64 = (m - 1 - low) / B
if h_max >= 0 {
let low_mod: i64 = low & (mod - 1)
subset = 0
while subset < (1 << fc) {
let i_mod: i64 = imods[subset]
let h: i64 = ((i_mod - low_mod) * invB) & (mod - 1)
if h <= h_max {
let ii: i64 = low + B * h
if ii < m && (ii & n) == n {
out = out + 1
}
}
subset = subset + 1
}
}
}
li = li + 1
}
free(n_digits); free(lows); free(free_pos); free(imods)
return out
}
function T(m: i64, n: i64) -> i64 {
if m <= n { return 0 }
let total: i64 = m - n
let not2: i64 = count_supermask_lt(m, n)
let not5: i64 = count_lucas_not_div_lt(m, n, 5)
let not10: i64 = count_not_div10_lt(m, n)
return total - not2 - not5 + not10
}
function main() -> i32 {
printf("%lld\n", T(1000000000000000000, 1000000000000 - 10))
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 digits_base_i64_i64_ptr_i64(int64_t x0, int64_t base, int64_t* out);
int64_t count_supermask_lt_i64_i64(int64_t limit, int64_t mask);
int64_t lucas_dp_i64_i64_i64_ptr_i64_ptr_i64_i64_ptr_i64(int64_t pos, int64_t tight, int64_t L, int64_t* lim_msb, int64_t* n_msb, int64_t base, int64_t* memo);
int64_t count_lucas_not_div_lt_i64_i64_i64(int64_t limit, int64_t n, int64_t base);
int64_t mod_inverse_odd_i64_i64(int64_t a0, int64_t mod);
int64_t count_not_div10_lt_i64_i64(int64_t m, int64_t n);
int64_t T_i64_i64(int64_t m, int64_t n);
int32_t main(void);
int64_t digits_base_i64_i64_ptr_i64(int64_t x0, int64_t base, int64_t* out) {
int64_t x = x0;
if (x == 0) {
out[0] = 0;
return 1;
}
int64_t n = 0;
while (x > 0) {
out[n] = FLOW_CHECKED_MOD((x), (base));
x = FLOW_CHECKED_DIV((x), (base));
n = (n + 1);
}
return n;
}
int64_t count_supermask_lt_i64_i64(int64_t limit, int64_t mask) {
if (limit <= 0) {
return 0;
}
int64_t bits = 0;
int64_t t = limit;
while (t > 0) {
bits = (bits + 1);
t = FLOW_CHECKED_DIV((t), (2));
}
int64_t dp_tight = 1;
int64_t dp_loose = 0;
int64_t p = (bits - 1);
while (p >= 0) {
int64_t lim_bit = (FLOW_CHECKED_SHR((limit), (p)) & 1);
int64_t forced = (FLOW_CHECKED_SHR((mask), (p)) & 1);
int64_t new_tight = 0;
int64_t new_loose = 0;
if (dp_loose != 0) {
if (forced == 1) {
new_loose = (new_loose + dp_loose);
} else {
new_loose = (new_loose + (dp_loose * 2));
}
}
if (dp_tight != 0) {
if (forced == 1) {
if (lim_bit == 1) {
new_tight = (new_tight + dp_tight);
}
} else {
if (lim_bit == 0) {
new_tight = (new_tight + dp_tight);
} else {
new_loose = (new_loose + dp_tight);
new_tight = (new_tight + dp_tight);
}
}
}
dp_tight = new_tight;
dp_loose = new_loose;
p = (p - 1);
}
return dp_loose;
}
int64_t lucas_dp_i64_i64_i64_ptr_i64_ptr_i64_i64_ptr_i64(int64_t pos, int64_t tight, int64_t L, int64_t* lim_msb, int64_t* n_msb, int64_t base, int64_t* memo) {
if (pos == L) {
return 1;
}
int64_t key = ((pos * 2) + tight);
if (memo[key] >= 0) {
return memo[key];
}
int64_t limd = lim_msb[pos];
int64_t mind = n_msb[pos];
int64_t maxd = (base - 1);
if (tight == 1) {
maxd = limd;
}
int64_t total = 0;
int64_t d = mind;
while (d <= maxd) {
int64_t nt = 0;
if ((tight == 1 && d == limd)) {
nt = 1;
}
total = (total + lucas_dp_i64_i64_i64_ptr_i64_ptr_i64_i64_ptr_i64((pos + 1), nt, L, lim_msb, n_msb, base, memo));
d = (d + 1);
}
memo[key] = total;
return total;
}
int64_t count_lucas_not_div_lt_i64_i64_i64(int64_t limit, int64_t n, int64_t base) {
if (limit <= 0) {
return 0;
}
int64_t upper = (limit - 1);
int64_t* lim_d = (int64_t*)(calloc(80, 8));
int64_t* n_d = (int64_t*)(calloc(80, 8));
int64_t ld = digits_base_i64_i64_ptr_i64(upper, base, lim_d);
int64_t nd = digits_base_i64_i64_ptr_i64(n, base, n_d);
int64_t L = ld;
if (nd > L) {
L = nd;
}
int64_t* lim_msb = (int64_t*)(calloc(L, 8));
int64_t* n_msb = (int64_t*)(calloc(L, 8));
int64_t i = 0;
while (i < L) {
int64_t li = 0;
if (((L - 1) - i) < ld) {
li = lim_d[((L - 1) - i)];
}
int64_t ni = 0;
if (((L - 1) - i) < nd) {
ni = n_d[((L - 1) - i)];
}
lim_msb[i] = li;
n_msb[i] = ni;
i = (i + 1);
}
int64_t* memo = (int64_t*)(calloc(((2 * L) + 2), 8));
i = 0;
while (i < ((2 * L) + 2)) {
memo[i] = (-1);
i = (i + 1);
}
int64_t ans = lucas_dp_i64_i64_i64_ptr_i64_ptr_i64_i64_ptr_i64(0, 1, L, lim_msb, n_msb, base, memo);
free(lim_d);
free(n_d);
free(lim_msb);
free(n_msb);
free(memo);
return ans;
}
int64_t mod_inverse_odd_i64_i64(int64_t a0, int64_t mod) {
int64_t a = FLOW_CHECKED_MOD((a0), (mod));
int64_t x = 1;
int64_t i = 0;
while (i < 6) {
int64_t ax = FLOW_CHECKED_MOD(((a * x)), (mod));
x = FLOW_CHECKED_MOD((FLOW_CHECKED_MOD(((x * (FLOW_CHECKED_MOD(((2 - ax)), (mod)) + mod))), (mod))), (mod));
i = (i + 1);
}
return FLOW_CHECKED_MOD((x), (mod));
}
int64_t count_not_div10_lt_i64_i64(int64_t m, int64_t n) {
if (m <= 0) {
return 0;
}
int64_t* n_digits = (int64_t*)(calloc(40, 8));
int64_t nd = digits_base_i64_i64_ptr_i64(n, 5, n_digits);
int64_t* lows = (int64_t*)(calloc(1, 8));
lows[0] = 0;
int64_t lc = 1;
int64_t pow5 = 1;
int64_t di = 0;
while (di < nd) {
int64_t dmin = n_digits[di];
int64_t newc = (lc * (5 - dmin));
int64_t* newlows = (int64_t*)(calloc(newc, 8));
int64_t k = 0;
int64_t i = 0;
while (i < lc) {
int64_t d = dmin;
while (d < 5) {
newlows[k] = (lows[i] + (d * pow5));
k = (k + 1);
d = (d + 1);
}
i = (i + 1);
}
free(lows);
lows = newlows;
lc = newc;
pow5 = (pow5 * 5);
di = (di + 1);
}
int64_t B = pow5;
int64_t max_h = FLOW_CHECKED_DIV(((m - 1)), (B));
int64_t kk = 1;
int64_t tmp = max_h;
while (tmp > 0) {
kk = (kk + 1);
tmp = FLOW_CHECKED_DIV((tmp), (2));
}
if (kk < 1) {
kk = 1;
}
int64_t mod = FLOW_CHECKED_SHL((1), (kk));
int64_t invB = mod_inverse_odd_i64_i64(FLOW_CHECKED_MOD((B), (mod)), mod);
int64_t required_low = (n & (mod - 1));
int64_t* free_pos = (int64_t*)(calloc(64, 8));
int64_t fc = 0;
int64_t b = 0;
while (b < kk) {
if ((FLOW_CHECKED_SHR((required_low), (b)) & 1) == 0) {
free_pos[fc] = b;
fc = (fc + 1);
}
b = (b + 1);
}
int64_t* imods = (int64_t*)(calloc(FLOW_CHECKED_SHL((1), (fc)), 8));
int64_t subset = 0;
while (subset < FLOW_CHECKED_SHL((1), (fc))) {
int64_t val = required_low;
int64_t j = 0;
while (j < fc) {
if ((FLOW_CHECKED_SHR((subset), (j)) & 1) == 1) {
val = (val | FLOW_CHECKED_SHL((1), (free_pos[j])));
}
j = (j + 1);
}
imods[subset] = val;
subset = (subset + 1);
}
int64_t out = 0;
int64_t li = 0;
while (li < lc) {
int64_t low = lows[li];
if (low < m) {
int64_t h_max = FLOW_CHECKED_DIV((((m - 1) - low)), (B));
if (h_max >= 0) {
int64_t low_mod = (low & (mod - 1));
subset = 0;
while (subset < FLOW_CHECKED_SHL((1), (fc))) {
int64_t i_mod = imods[subset];
int64_t h = (((i_mod - low_mod) * invB) & (mod - 1));
if (h <= h_max) {
int64_t ii = (low + (B * h));
if ((ii < m && (ii & n) == n)) {
out = (out + 1);
}
}
subset = (subset + 1);
}
}
}
li = (li + 1);
}
free(n_digits);
free(lows);
free(free_pos);
free(imods);
return out;
}
int64_t T_i64_i64(int64_t m, int64_t n) {
if (m <= n) {
return 0;
}
int64_t total = (m - n);
int64_t not2 = count_supermask_lt_i64_i64(m, n);
int64_t not5 = count_lucas_not_div_lt_i64_i64_i64(m, n, 5);
int64_t not10 = count_not_div10_lt_i64_i64(m, n);
return (((total - not2) - not5) + not10);
}
int32_t main(void) {
printf("%lld\n", T_i64_i64(1000000000000000000, (1000000000000 - 10)));
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
func.func @digits_base(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr) -> 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.load %1 : !llvm.ptr -> i64
%3 = arith.constant 0 : i32
%5 = arith.extsi %3 : i32 to i64
%4 = arith.cmpi eq, %2, %5 : i64
cf.cond_br %4, ^bb0, ^bb1
^bb0:
%6 = arith.constant 0 : i32
%7 = arith.constant 0 : i32
%8 = arith.extsi %6 : i32 to i64
%9 = arith.extsi %7 : i32 to i64
%10 = llvm.getelementptr %arg2[%9] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %8, %10 : i64, !llvm.ptr
%11 = arith.constant 1 : i32
%12 = arith.extsi %11 : i32 to i64
func.return %12 : i64
^bb1:
cf.br ^bb2
^bb2:
%13 = arith.constant 0 : i32
%14 = arith.extsi %13 : i32 to i64
%15 = llvm.mlir.constant(1 : i64) : i64
%16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
llvm.store %14, %16 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%17 = llvm.load %1 : !llvm.ptr -> i64
%18 = arith.constant 0 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi sgt, %17, %20 : i64
cf.cond_br %19, ^bb4, ^bb5
^bb4:
%21 = llvm.load %1 : !llvm.ptr -> i64
%22 = arith.remsi %21, %arg1 : i64
%23 = llvm.load %16 : !llvm.ptr -> i64
%24 = llvm.getelementptr %arg2[%23] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %22, %24 : i64, !llvm.ptr
%25 = llvm.load %1 : !llvm.ptr -> i64
%26 = arith.divsi %25, %arg1 : i64
llvm.store %26, %1 : i64, !llvm.ptr
%27 = llvm.load %16 : !llvm.ptr -> i64
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.addi %27, %30 : i64
llvm.store %29, %16 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%31 = llvm.load %16 : !llvm.ptr -> i64
func.return %31 : i64
}
func.func @count_supermask_lt(%arg0: i64, %arg1: i64) -> i64 {
%32 = arith.constant 0 : i32
%34 = arith.extsi %32 : i32 to i64
%33 = arith.cmpi sle, %arg0, %34 : i64
cf.cond_br %33, ^bb6, ^bb7
^bb6:
%35 = arith.constant 0 : i32
%36 = arith.extsi %35 : i32 to i64
func.return %36 : i64
^bb7:
cf.br ^bb8
^bb8:
%37 = arith.constant 0 : i32
%38 = arith.extsi %37 : i32 to i64
%39 = llvm.mlir.constant(1 : i64) : i64
%40 = llvm.alloca %39 x i64 : (i64) -> !llvm.ptr
llvm.store %38, %40 : i64, !llvm.ptr
%41 = llvm.mlir.constant(1 : i64) : i64
%42 = llvm.alloca %41 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %42 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%43 = llvm.load %42 : !llvm.ptr -> i64
%44 = arith.constant 0 : i32
%46 = arith.extsi %44 : i32 to i64
%45 = arith.cmpi sgt, %43, %46 : i64
cf.cond_br %45, ^bb10, ^bb11
^bb10:
%47 = llvm.load %40 : !llvm.ptr -> i64
%48 = arith.constant 1 : i32
%50 = arith.extsi %48 : i32 to i64
%49 = arith.addi %47, %50 : i64
llvm.store %49, %40 : i64, !llvm.ptr
%51 = llvm.load %42 : !llvm.ptr -> i64
%52 = arith.constant 2 : i32
%54 = arith.extsi %52 : i32 to i64
%53 = arith.divsi %51, %54 : i64
llvm.store %53, %42 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
%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 0 : 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 = llvm.load %40 : !llvm.ptr -> i64
%64 = arith.constant 1 : i32
%66 = arith.extsi %64 : i32 to i64
%65 = arith.subi %63, %66 : i64
%67 = llvm.mlir.constant(1 : i64) : i64
%68 = llvm.alloca %67 x i64 : (i64) -> !llvm.ptr
llvm.store %65, %68 : i64, !llvm.ptr
cf.br ^bb12
^bb12:
%69 = llvm.load %68 : !llvm.ptr -> i64
%70 = arith.constant 0 : i32
%72 = arith.extsi %70 : i32 to i64
%71 = arith.cmpi sge, %69, %72 : i64
cf.cond_br %71, ^bb13, ^bb14
^bb13:
%73 = llvm.load %68 : !llvm.ptr -> i64
%74 = arith.shrsi %arg0, %73 : i64
%75 = arith.constant 1 : i32
%77 = arith.extsi %75 : i32 to i64
%76 = arith.andi %74, %77 : i64
%78 = llvm.load %68 : !llvm.ptr -> i64
%79 = arith.shrsi %arg1, %78 : i64
%80 = arith.constant 1 : i32
%82 = arith.extsi %80 : i32 to i64
%81 = arith.andi %79, %82 : i64
%83 = arith.constant 0 : i32
%84 = arith.extsi %83 : i32 to i64
%85 = llvm.mlir.constant(1 : i64) : i64
%86 = llvm.alloca %85 x i64 : (i64) -> !llvm.ptr
llvm.store %84, %86 : i64, !llvm.ptr
%87 = arith.constant 0 : i32
%88 = arith.extsi %87 : i32 to i64
%89 = llvm.mlir.constant(1 : i64) : i64
%90 = llvm.alloca %89 x i64 : (i64) -> !llvm.ptr
llvm.store %88, %90 : i64, !llvm.ptr
%91 = llvm.load %62 : !llvm.ptr -> i64
%92 = arith.constant 0 : i32
%94 = arith.extsi %92 : i32 to i64
%93 = arith.cmpi ne, %91, %94 : i64
cf.cond_br %93, ^bb15, ^bb16
^bb15:
%95 = arith.constant 1 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.cmpi eq, %81, %97 : i64
cf.cond_br %96, ^bb18, ^bb19
^bb18:
%98 = llvm.load %90 : !llvm.ptr -> i64
%99 = llvm.load %62 : !llvm.ptr -> i64
%100 = arith.addi %98, %99 : i64
llvm.store %100, %90 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
%101 = llvm.load %90 : !llvm.ptr -> i64
%102 = llvm.load %62 : !llvm.ptr -> i64
%103 = arith.constant 2 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.muli %102, %105 : i64
%106 = arith.addi %101, %104 : i64
llvm.store %106, %90 : i64, !llvm.ptr
cf.br ^bb20
^bb20:
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%107 = llvm.load %58 : !llvm.ptr -> i64
%108 = arith.constant 0 : i32
%110 = arith.extsi %108 : i32 to i64
%109 = arith.cmpi ne, %107, %110 : i64
cf.cond_br %109, ^bb21, ^bb22
^bb21:
%111 = arith.constant 1 : i32
%113 = arith.extsi %111 : i32 to i64
%112 = arith.cmpi eq, %81, %113 : i64
cf.cond_br %112, ^bb24, ^bb25
^bb24:
%114 = arith.constant 1 : i32
%116 = arith.extsi %114 : i32 to i64
%115 = arith.cmpi eq, %76, %116 : i64
cf.cond_br %115, ^bb27, ^bb28
^bb27:
%117 = llvm.load %86 : !llvm.ptr -> i64
%118 = llvm.load %58 : !llvm.ptr -> i64
%119 = arith.addi %117, %118 : i64
llvm.store %119, %86 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
cf.br ^bb26
^bb25:
%120 = arith.constant 0 : i32
%122 = arith.extsi %120 : i32 to i64
%121 = arith.cmpi eq, %76, %122 : i64
cf.cond_br %121, ^bb30, ^bb31
^bb30:
%123 = llvm.load %86 : !llvm.ptr -> i64
%124 = llvm.load %58 : !llvm.ptr -> i64
%125 = arith.addi %123, %124 : i64
llvm.store %125, %86 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
%126 = llvm.load %90 : !llvm.ptr -> i64
%127 = llvm.load %58 : !llvm.ptr -> i64
%128 = arith.addi %126, %127 : i64
llvm.store %128, %90 : i64, !llvm.ptr
%129 = llvm.load %86 : !llvm.ptr -> i64
%130 = llvm.load %58 : !llvm.ptr -> i64
%131 = arith.addi %129, %130 : i64
llvm.store %131, %86 : i64, !llvm.ptr
cf.br ^bb32
^bb32:
cf.br ^bb26
^bb26:
cf.br ^bb23
^bb22:
cf.br ^bb23
^bb23:
%132 = llvm.load %86 : !llvm.ptr -> i64
llvm.store %132, %58 : i64, !llvm.ptr
%133 = llvm.load %90 : !llvm.ptr -> i64
llvm.store %133, %62 : i64, !llvm.ptr
%134 = llvm.load %68 : !llvm.ptr -> i64
%135 = arith.constant 1 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.subi %134, %137 : i64
llvm.store %136, %68 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%138 = llvm.load %62 : !llvm.ptr -> i64
func.return %138 : i64
}
func.func @lucas_dp(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: !llvm.ptr, %arg4: !llvm.ptr, %arg5: i64, %arg6: !llvm.ptr) -> i64 {
%139 = arith.cmpi eq, %arg0, %arg2 : i64
cf.cond_br %139, ^bb33, ^bb34
^bb33:
%140 = arith.constant 1 : i32
%141 = arith.extsi %140 : i32 to i64
func.return %141 : i64
^bb34:
cf.br ^bb35
^bb35:
%142 = arith.constant 2 : i32
%144 = arith.extsi %142 : i32 to i64
%143 = arith.muli %arg0, %144 : i64
%145 = arith.addi %143, %arg1 : i64
%147 = llvm.getelementptr %arg6[%145] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%146 = llvm.load %147 : !llvm.ptr -> i64
%148 = arith.constant 0 : i32
%150 = arith.extsi %148 : i32 to i64
%149 = arith.cmpi sge, %146, %150 : i64
cf.cond_br %149, ^bb36, ^bb37
^bb36:
%152 = llvm.getelementptr %arg6[%145] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%151 = llvm.load %152 : !llvm.ptr -> i64
func.return %151 : i64
^bb37:
cf.br ^bb38
^bb38:
%154 = llvm.getelementptr %arg3[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%153 = llvm.load %154 : !llvm.ptr -> i64
%156 = llvm.getelementptr %arg4[%arg0] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%155 = llvm.load %156 : !llvm.ptr -> i64
%157 = arith.constant 1 : i32
%159 = arith.extsi %157 : i32 to i64
%158 = arith.subi %arg5, %159 : i64
%160 = llvm.mlir.constant(1 : i64) : i64
%161 = llvm.alloca %160 x i64 : (i64) -> !llvm.ptr
llvm.store %158, %161 : i64, !llvm.ptr
%162 = arith.constant 1 : i32
%164 = arith.extsi %162 : i32 to i64
%163 = arith.cmpi eq, %arg1, %164 : i64
cf.cond_br %163, ^bb39, ^bb40
^bb39:
llvm.store %153, %161 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%165 = arith.constant 0 : i32
%166 = arith.extsi %165 : i32 to i64
%167 = llvm.mlir.constant(1 : i64) : i64
%168 = llvm.alloca %167 x i64 : (i64) -> !llvm.ptr
llvm.store %166, %168 : i64, !llvm.ptr
%169 = llvm.mlir.constant(1 : i64) : i64
%170 = llvm.alloca %169 x i64 : (i64) -> !llvm.ptr
llvm.store %155, %170 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%171 = llvm.load %170 : !llvm.ptr -> i64
%172 = llvm.load %161 : !llvm.ptr -> i64
%173 = arith.cmpi sle, %171, %172 : i64
cf.cond_br %173, ^bb43, ^bb44
^bb43:
%174 = arith.constant 0 : i32
%175 = arith.extsi %174 : i32 to i64
%176 = arith.constant 1 : i32
%178 = arith.extsi %176 : i32 to i64
%177 = arith.cmpi eq, %arg1, %178 : i64
%179 = scf.if %177 -> (i1) {
%180 = llvm.load %170 : !llvm.ptr -> i64
%181 = arith.cmpi eq, %180, %153 : i64
scf.yield %181 : i1
} else {
%182 = arith.constant false
scf.yield %182 : i1
}
%183 = scf.if %179 -> (i64) {
%184 = arith.constant 1 : i32
%185 = arith.extsi %184 : i32 to i64
scf.yield %185 : i64
} else {
scf.yield %175 : i64
}
%186 = llvm.load %168 : !llvm.ptr -> i64
%188 = arith.constant 1 : i32
%190 = arith.extsi %188 : i32 to i64
%189 = arith.addi %arg0, %190 : i64
%187 = func.call @lucas_dp(%189, %183, %arg2, %arg3, %arg4, %arg5, %arg6) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr) -> i64
%191 = arith.addi %186, %187 : i64
llvm.store %191, %168 : i64, !llvm.ptr
%192 = llvm.load %170 : !llvm.ptr -> i64
%193 = arith.constant 1 : i32
%195 = arith.extsi %193 : i32 to i64
%194 = arith.addi %192, %195 : i64
llvm.store %194, %170 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%196 = llvm.load %168 : !llvm.ptr -> i64
%197 = llvm.getelementptr %arg6[%145] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %196, %197 : i64, !llvm.ptr
%198 = llvm.load %168 : !llvm.ptr -> i64
func.return %198 : i64
}
func.func @count_lucas_not_div_lt(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%199 = arith.constant 0 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.cmpi sle, %arg0, %201 : i64
cf.cond_br %200, ^bb45, ^bb46
^bb45:
%202 = arith.constant 0 : i32
%203 = arith.extsi %202 : i32 to i64
func.return %203 : i64
^bb46:
cf.br ^bb47
^bb47:
%204 = arith.constant 1 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.subi %arg0, %206 : i64
%208 = arith.constant 80 : i32
%209 = arith.constant 8 : i32
%210 = arith.extsi %208 : i32 to i64
%211 = arith.extsi %209 : i32 to i64
%207 = func.call @calloc(%210, %211) : (i64, i64) -> !llvm.ptr
%213 = arith.constant 80 : i32
%214 = arith.constant 8 : i32
%215 = arith.extsi %213 : i32 to i64
%216 = arith.extsi %214 : i32 to i64
%212 = func.call @calloc(%215, %216) : (i64, i64) -> !llvm.ptr
%217 = func.call @digits_base(%205, %arg2, %207) : (i64, i64, !llvm.ptr) -> i64
%218 = func.call @digits_base(%arg1, %arg2, %212) : (i64, i64, !llvm.ptr) -> i64
%219 = llvm.mlir.constant(1 : i64) : i64
%220 = llvm.alloca %219 x i64 : (i64) -> !llvm.ptr
llvm.store %217, %220 : i64, !llvm.ptr
%221 = llvm.load %220 : !llvm.ptr -> i64
%222 = arith.cmpi sgt, %218, %221 : i64
cf.cond_br %222, ^bb48, ^bb49
^bb48:
llvm.store %218, %220 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%224 = llvm.load %220 : !llvm.ptr -> i64
%225 = arith.constant 8 : i32
%226 = arith.extsi %225 : i32 to i64
%223 = func.call @calloc(%224, %226) : (i64, i64) -> !llvm.ptr
%228 = llvm.load %220 : !llvm.ptr -> i64
%229 = arith.constant 8 : i32
%230 = arith.extsi %229 : i32 to i64
%227 = func.call @calloc(%228, %230) : (i64, i64) -> !llvm.ptr
%231 = arith.constant 0 : i32
%232 = arith.extsi %231 : i32 to i64
%233 = llvm.mlir.constant(1 : i64) : i64
%234 = llvm.alloca %233 x i64 : (i64) -> !llvm.ptr
llvm.store %232, %234 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%235 = llvm.load %234 : !llvm.ptr -> i64
%236 = llvm.load %220 : !llvm.ptr -> i64
%237 = arith.cmpi slt, %235, %236 : i64
cf.cond_br %237, ^bb52, ^bb53
^bb52:
%238 = arith.constant 0 : i32
%239 = arith.extsi %238 : i32 to i64
%240 = llvm.load %220 : !llvm.ptr -> i64
%241 = arith.constant 1 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.subi %240, %243 : i64
%244 = llvm.load %234 : !llvm.ptr -> i64
%245 = arith.subi %242, %244 : i64
%246 = arith.cmpi slt, %245, %217 : i64
%247 = scf.if %246 -> (i64) {
%249 = llvm.load %220 : !llvm.ptr -> i64
%250 = arith.constant 1 : i32
%252 = arith.extsi %250 : i32 to i64
%251 = arith.subi %249, %252 : i64
%253 = llvm.load %234 : !llvm.ptr -> i64
%254 = arith.subi %251, %253 : i64
%255 = llvm.getelementptr %207[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%248 = llvm.load %255 : !llvm.ptr -> i64
scf.yield %248 : i64
} else {
scf.yield %239 : i64
}
%256 = arith.constant 0 : i32
%257 = arith.extsi %256 : i32 to i64
%258 = llvm.load %220 : !llvm.ptr -> i64
%259 = arith.constant 1 : i32
%261 = arith.extsi %259 : i32 to i64
%260 = arith.subi %258, %261 : i64
%262 = llvm.load %234 : !llvm.ptr -> i64
%263 = arith.subi %260, %262 : i64
%264 = arith.cmpi slt, %263, %218 : i64
%265 = scf.if %264 -> (i64) {
%267 = llvm.load %220 : !llvm.ptr -> i64
%268 = arith.constant 1 : i32
%270 = arith.extsi %268 : i32 to i64
%269 = arith.subi %267, %270 : i64
%271 = llvm.load %234 : !llvm.ptr -> i64
%272 = arith.subi %269, %271 : i64
%273 = llvm.getelementptr %212[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%266 = llvm.load %273 : !llvm.ptr -> i64
scf.yield %266 : i64
} else {
scf.yield %257 : i64
}
%274 = llvm.load %234 : !llvm.ptr -> i64
%275 = llvm.getelementptr %223[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %247, %275 : i64, !llvm.ptr
%276 = llvm.load %234 : !llvm.ptr -> i64
%277 = llvm.getelementptr %227[%276] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %265, %277 : i64, !llvm.ptr
%278 = llvm.load %234 : !llvm.ptr -> i64
%279 = arith.constant 1 : i32
%281 = arith.extsi %279 : i32 to i64
%280 = arith.addi %278, %281 : i64
llvm.store %280, %234 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
%283 = arith.constant 2 : i32
%284 = llvm.load %220 : !llvm.ptr -> i64
%286 = arith.extsi %283 : i32 to i64
%285 = arith.muli %286, %284 : i64
%287 = arith.constant 2 : i32
%289 = arith.extsi %287 : i32 to i64
%288 = arith.addi %285, %289 : i64
%290 = arith.constant 8 : i32
%291 = arith.extsi %290 : i32 to i64
%282 = func.call @calloc(%288, %291) : (i64, i64) -> !llvm.ptr
%292 = arith.constant 0 : i32
%293 = arith.extsi %292 : i32 to i64
llvm.store %293, %234 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%294 = llvm.load %234 : !llvm.ptr -> i64
%295 = arith.constant 2 : i32
%296 = llvm.load %220 : !llvm.ptr -> i64
%298 = arith.extsi %295 : i32 to i64
%297 = arith.muli %298, %296 : i64
%299 = arith.constant 2 : i32
%301 = arith.extsi %299 : i32 to i64
%300 = arith.addi %297, %301 : i64
%302 = arith.cmpi slt, %294, %300 : i64
cf.cond_br %302, ^bb55, ^bb56
^bb55:
%303 = arith.constant 1 : i32
%305 = arith.constant 0 : i32
%304 = arith.subi %305, %303 : i32
%306 = llvm.load %234 : !llvm.ptr -> i64
%307 = arith.extsi %304 : i32 to i64
%308 = llvm.getelementptr %282[%306] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %307, %308 : i64, !llvm.ptr
%309 = llvm.load %234 : !llvm.ptr -> i64
%310 = arith.constant 1 : i32
%312 = arith.extsi %310 : i32 to i64
%311 = arith.addi %309, %312 : i64
llvm.store %311, %234 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%314 = arith.constant 0 : i32
%315 = arith.constant 1 : i32
%316 = llvm.load %220 : !llvm.ptr -> i64
%317 = arith.extsi %314 : i32 to i64
%318 = arith.extsi %315 : i32 to i64
%313 = func.call @lucas_dp(%317, %318, %316, %223, %227, %arg2, %282) : (i64, i64, i64, !llvm.ptr, !llvm.ptr, i64, !llvm.ptr) -> i64
func.call @free(%207) : (!llvm.ptr) -> ()
func.call @free(%212) : (!llvm.ptr) -> ()
func.call @free(%223) : (!llvm.ptr) -> ()
func.call @free(%227) : (!llvm.ptr) -> ()
func.call @free(%282) : (!llvm.ptr) -> ()
func.return %313 : i64
}
func.func @mod_inverse_odd(%arg0: i64, %arg1: i64) -> i64 {
%324 = arith.remsi %arg0, %arg1 : i64
%325 = llvm.mlir.constant(1 : i64) : i64
%326 = llvm.alloca %325 x i64 : (i64) -> !llvm.ptr
llvm.store %324, %326 : i64, !llvm.ptr
%327 = arith.constant 1 : i32
%328 = arith.extsi %327 : i32 to i64
%329 = llvm.mlir.constant(1 : i64) : i64
%330 = llvm.alloca %329 x i64 : (i64) -> !llvm.ptr
llvm.store %328, %330 : i64, !llvm.ptr
%331 = arith.constant 0 : i32
%332 = arith.extsi %331 : i32 to i64
%333 = llvm.mlir.constant(1 : i64) : i64
%334 = llvm.alloca %333 x i64 : (i64) -> !llvm.ptr
llvm.store %332, %334 : i64, !llvm.ptr
cf.br ^bb57
^bb57:
%335 = llvm.load %334 : !llvm.ptr -> i64
%336 = arith.constant 6 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.cmpi slt, %335, %338 : i64
cf.cond_br %337, ^bb58, ^bb59
^bb58:
%339 = llvm.load %326 : !llvm.ptr -> i64
%340 = llvm.load %330 : !llvm.ptr -> i64
%341 = arith.muli %339, %340 : i64
%342 = arith.remsi %341, %arg1 : i64
%343 = llvm.load %330 : !llvm.ptr -> i64
%344 = arith.constant 2 : i32
%346 = arith.extsi %344 : i32 to i64
%345 = arith.subi %346, %342 : i64
%347 = arith.remsi %345, %arg1 : i64
%348 = arith.addi %347, %arg1 : i64
%349 = arith.muli %343, %348 : i64
%350 = arith.remsi %349, %arg1 : i64
%351 = arith.remsi %350, %arg1 : i64
llvm.store %351, %330 : i64, !llvm.ptr
%352 = llvm.load %334 : !llvm.ptr -> i64
%353 = arith.constant 1 : i32
%355 = arith.extsi %353 : i32 to i64
%354 = arith.addi %352, %355 : i64
llvm.store %354, %334 : i64, !llvm.ptr
cf.br ^bb57
^bb59:
%356 = llvm.load %330 : !llvm.ptr -> i64
%357 = arith.remsi %356, %arg1 : i64
func.return %357 : i64
}
func.func @count_not_div10_lt(%arg0: i64, %arg1: i64) -> i64 {
%358 = arith.constant 0 : i32
%360 = arith.extsi %358 : i32 to i64
%359 = arith.cmpi sle, %arg0, %360 : i64
cf.cond_br %359, ^bb60, ^bb61
^bb60:
%361 = arith.constant 0 : i32
%362 = arith.extsi %361 : i32 to i64
func.return %362 : i64
^bb61:
cf.br ^bb62
^bb62:
%364 = arith.constant 40 : i32
%365 = arith.constant 8 : i32
%366 = arith.extsi %364 : i32 to i64
%367 = arith.extsi %365 : i32 to i64
%363 = func.call @calloc(%366, %367) : (i64, i64) -> !llvm.ptr
%369 = arith.constant 5 : i32
%370 = arith.extsi %369 : i32 to i64
%368 = func.call @digits_base(%arg1, %370, %363) : (i64, i64, !llvm.ptr) -> i64
%372 = arith.constant 1 : i32
%373 = arith.constant 8 : i32
%374 = arith.extsi %372 : i32 to i64
%375 = arith.extsi %373 : i32 to i64
%371 = func.call @calloc(%374, %375) : (i64, i64) -> !llvm.ptr
%376 = llvm.mlir.constant(1 : i64) : i64
%377 = llvm.alloca %376 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %371, %377 : !llvm.ptr, !llvm.ptr
%378 = arith.constant 0 : i32
%379 = llvm.load %377 : !llvm.ptr -> !llvm.ptr
%380 = arith.constant 0 : i32
%381 = arith.extsi %378 : i32 to i64
%382 = arith.extsi %380 : i32 to i64
%383 = llvm.getelementptr %379[%382] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %381, %383 : i64, !llvm.ptr
%384 = arith.constant 1 : i32
%385 = arith.extsi %384 : i32 to i64
%386 = llvm.mlir.constant(1 : i64) : i64
%387 = llvm.alloca %386 x i64 : (i64) -> !llvm.ptr
llvm.store %385, %387 : i64, !llvm.ptr
%388 = arith.constant 1 : i32
%389 = arith.extsi %388 : i32 to i64
%390 = llvm.mlir.constant(1 : i64) : i64
%391 = llvm.alloca %390 x i64 : (i64) -> !llvm.ptr
llvm.store %389, %391 : i64, !llvm.ptr
%392 = arith.constant 0 : i32
%393 = arith.extsi %392 : i32 to i64
%394 = llvm.mlir.constant(1 : i64) : i64
%395 = llvm.alloca %394 x i64 : (i64) -> !llvm.ptr
llvm.store %393, %395 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%396 = llvm.load %395 : !llvm.ptr -> i64
%397 = arith.cmpi slt, %396, %368 : i64
cf.cond_br %397, ^bb64, ^bb65
^bb64:
%399 = llvm.load %395 : !llvm.ptr -> i64
%400 = llvm.getelementptr %363[%399] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%398 = llvm.load %400 : !llvm.ptr -> i64
%401 = llvm.load %387 : !llvm.ptr -> i64
%402 = arith.constant 5 : i32
%404 = arith.extsi %402 : i32 to i64
%403 = arith.subi %404, %398 : i64
%405 = arith.muli %401, %403 : i64
%407 = arith.constant 8 : i32
%408 = arith.extsi %407 : i32 to i64
%406 = func.call @calloc(%405, %408) : (i64, i64) -> !llvm.ptr
%409 = arith.constant 0 : i32
%410 = arith.extsi %409 : i32 to i64
%411 = llvm.mlir.constant(1 : i64) : i64
%412 = llvm.alloca %411 x i64 : (i64) -> !llvm.ptr
llvm.store %410, %412 : i64, !llvm.ptr
%413 = arith.constant 0 : i32
%414 = arith.extsi %413 : i32 to i64
%415 = llvm.mlir.constant(1 : i64) : i64
%416 = llvm.alloca %415 x i64 : (i64) -> !llvm.ptr
llvm.store %414, %416 : i64, !llvm.ptr
cf.br ^bb66
^bb66:
%417 = llvm.load %416 : !llvm.ptr -> i64
%418 = llvm.load %387 : !llvm.ptr -> i64
%419 = arith.cmpi slt, %417, %418 : i64
cf.cond_br %419, ^bb67, ^bb68
^bb67:
%420 = llvm.mlir.constant(1 : i64) : i64
%421 = llvm.alloca %420 x i64 : (i64) -> !llvm.ptr
llvm.store %398, %421 : i64, !llvm.ptr
cf.br ^bb69
^bb69:
%422 = llvm.load %421 : !llvm.ptr -> i64
%423 = arith.constant 5 : i32
%425 = arith.extsi %423 : i32 to i64
%424 = arith.cmpi slt, %422, %425 : i64
cf.cond_br %424, ^bb70, ^bb71
^bb70:
%427 = llvm.load %377 : !llvm.ptr -> !llvm.ptr
%428 = llvm.load %416 : !llvm.ptr -> i64
%429 = llvm.getelementptr %427[%428] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%426 = llvm.load %429 : !llvm.ptr -> i64
%430 = llvm.load %421 : !llvm.ptr -> i64
%431 = llvm.load %391 : !llvm.ptr -> i64
%432 = arith.muli %430, %431 : i64
%433 = arith.addi %426, %432 : i64
%434 = llvm.load %412 : !llvm.ptr -> i64
%435 = llvm.getelementptr %406[%434] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %433, %435 : i64, !llvm.ptr
%436 = llvm.load %412 : !llvm.ptr -> i64
%437 = arith.constant 1 : i32
%439 = arith.extsi %437 : i32 to i64
%438 = arith.addi %436, %439 : i64
llvm.store %438, %412 : i64, !llvm.ptr
%440 = llvm.load %421 : !llvm.ptr -> i64
%441 = arith.constant 1 : i32
%443 = arith.extsi %441 : i32 to i64
%442 = arith.addi %440, %443 : i64
llvm.store %442, %421 : i64, !llvm.ptr
cf.br ^bb69
^bb71:
%444 = llvm.load %416 : !llvm.ptr -> i64
%445 = arith.constant 1 : i32
%447 = arith.extsi %445 : i32 to i64
%446 = arith.addi %444, %447 : i64
llvm.store %446, %416 : i64, !llvm.ptr
cf.br ^bb66
^bb68:
%449 = llvm.load %377 : !llvm.ptr -> !llvm.ptr
func.call @free(%449) : (!llvm.ptr) -> ()
llvm.store %406, %377 : !llvm.ptr, !llvm.ptr
llvm.store %405, %387 : i64, !llvm.ptr
%450 = llvm.load %391 : !llvm.ptr -> i64
%451 = arith.constant 5 : i32
%453 = arith.extsi %451 : i32 to i64
%452 = arith.muli %450, %453 : i64
llvm.store %452, %391 : i64, !llvm.ptr
%454 = llvm.load %395 : !llvm.ptr -> i64
%455 = arith.constant 1 : i32
%457 = arith.extsi %455 : i32 to i64
%456 = arith.addi %454, %457 : i64
llvm.store %456, %395 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%458 = llvm.load %391 : !llvm.ptr -> i64
%459 = arith.constant 1 : i32
%461 = arith.extsi %459 : i32 to i64
%460 = arith.subi %arg0, %461 : i64
%462 = arith.divsi %460, %458 : i64
%463 = arith.constant 1 : i32
%464 = arith.extsi %463 : i32 to i64
%465 = llvm.mlir.constant(1 : i64) : i64
%466 = llvm.alloca %465 x i64 : (i64) -> !llvm.ptr
llvm.store %464, %466 : i64, !llvm.ptr
%467 = llvm.mlir.constant(1 : i64) : i64
%468 = llvm.alloca %467 x i64 : (i64) -> !llvm.ptr
llvm.store %462, %468 : i64, !llvm.ptr
cf.br ^bb72
^bb72:
%469 = llvm.load %468 : !llvm.ptr -> i64
%470 = arith.constant 0 : i32
%472 = arith.extsi %470 : i32 to i64
%471 = arith.cmpi sgt, %469, %472 : i64
cf.cond_br %471, ^bb73, ^bb74
^bb73:
%473 = llvm.load %466 : !llvm.ptr -> i64
%474 = arith.constant 1 : i32
%476 = arith.extsi %474 : i32 to i64
%475 = arith.addi %473, %476 : i64
llvm.store %475, %466 : i64, !llvm.ptr
%477 = llvm.load %468 : !llvm.ptr -> i64
%478 = arith.constant 2 : i32
%480 = arith.extsi %478 : i32 to i64
%479 = arith.divsi %477, %480 : i64
llvm.store %479, %468 : i64, !llvm.ptr
cf.br ^bb72
^bb74:
%481 = llvm.load %466 : !llvm.ptr -> i64
%482 = arith.constant 1 : i32
%484 = arith.extsi %482 : i32 to i64
%483 = arith.cmpi slt, %481, %484 : i64
cf.cond_br %483, ^bb75, ^bb76
^bb75:
%485 = arith.constant 1 : i32
%486 = arith.extsi %485 : i32 to i64
llvm.store %486, %466 : i64, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
%487 = arith.constant 1 : i32
%488 = llvm.load %466 : !llvm.ptr -> i64
%490 = arith.extsi %487 : i32 to i64
%489 = arith.shli %490, %488 : i64
%492 = arith.remsi %458, %489 : i64
%491 = func.call @mod_inverse_odd(%492, %489) : (i64, i64) -> i64
%493 = arith.constant 1 : i32
%495 = arith.extsi %493 : i32 to i64
%494 = arith.subi %489, %495 : i64
%496 = arith.andi %arg1, %494 : i64
%498 = arith.constant 64 : i32
%499 = arith.constant 8 : i32
%500 = arith.extsi %498 : i32 to i64
%501 = arith.extsi %499 : i32 to i64
%497 = func.call @calloc(%500, %501) : (i64, i64) -> !llvm.ptr
%502 = arith.constant 0 : i32
%503 = arith.extsi %502 : i32 to i64
%504 = llvm.mlir.constant(1 : i64) : i64
%505 = llvm.alloca %504 x i64 : (i64) -> !llvm.ptr
llvm.store %503, %505 : i64, !llvm.ptr
%506 = arith.constant 0 : i32
%507 = arith.extsi %506 : i32 to i64
%508 = llvm.mlir.constant(1 : i64) : i64
%509 = llvm.alloca %508 x i64 : (i64) -> !llvm.ptr
llvm.store %507, %509 : i64, !llvm.ptr
cf.br ^bb78
^bb78:
%510 = llvm.load %509 : !llvm.ptr -> i64
%511 = llvm.load %466 : !llvm.ptr -> i64
%512 = arith.cmpi slt, %510, %511 : i64
cf.cond_br %512, ^bb79, ^bb80
^bb79:
%513 = llvm.load %509 : !llvm.ptr -> i64
%514 = arith.shrsi %496, %513 : i64
%515 = arith.constant 1 : i32
%517 = arith.extsi %515 : i32 to i64
%516 = arith.andi %514, %517 : i64
%518 = arith.constant 0 : i32
%520 = arith.extsi %518 : i32 to i64
%519 = arith.cmpi eq, %516, %520 : i64
cf.cond_br %519, ^bb81, ^bb82
^bb81:
%521 = llvm.load %509 : !llvm.ptr -> i64
%522 = llvm.load %505 : !llvm.ptr -> i64
%523 = llvm.getelementptr %497[%522] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %521, %523 : i64, !llvm.ptr
%524 = llvm.load %505 : !llvm.ptr -> i64
%525 = arith.constant 1 : i32
%527 = arith.extsi %525 : i32 to i64
%526 = arith.addi %524, %527 : i64
llvm.store %526, %505 : i64, !llvm.ptr
cf.br ^bb83
^bb82:
cf.br ^bb83
^bb83:
%528 = llvm.load %509 : !llvm.ptr -> i64
%529 = arith.constant 1 : i32
%531 = arith.extsi %529 : i32 to i64
%530 = arith.addi %528, %531 : i64
llvm.store %530, %509 : i64, !llvm.ptr
cf.br ^bb78
^bb80:
%533 = arith.constant 1 : i32
%534 = llvm.load %505 : !llvm.ptr -> i64
%536 = arith.extsi %533 : i32 to i64
%535 = arith.shli %536, %534 : i64
%537 = arith.constant 8 : i32
%538 = arith.extsi %537 : i32 to i64
%532 = func.call @calloc(%535, %538) : (i64, i64) -> !llvm.ptr
%539 = arith.constant 0 : i32
%540 = arith.extsi %539 : i32 to i64
%541 = llvm.mlir.constant(1 : i64) : i64
%542 = llvm.alloca %541 x i64 : (i64) -> !llvm.ptr
llvm.store %540, %542 : i64, !llvm.ptr
cf.br ^bb84
^bb84:
%543 = llvm.load %542 : !llvm.ptr -> i64
%544 = arith.constant 1 : i32
%545 = llvm.load %505 : !llvm.ptr -> i64
%547 = arith.extsi %544 : i32 to i64
%546 = arith.shli %547, %545 : i64
%548 = arith.cmpi slt, %543, %546 : i64
cf.cond_br %548, ^bb85, ^bb86
^bb85:
%549 = llvm.mlir.constant(1 : i64) : i64
%550 = llvm.alloca %549 x i64 : (i64) -> !llvm.ptr
llvm.store %496, %550 : i64, !llvm.ptr
%551 = arith.constant 0 : i32
%552 = arith.extsi %551 : i32 to i64
%553 = llvm.mlir.constant(1 : i64) : i64
%554 = llvm.alloca %553 x i64 : (i64) -> !llvm.ptr
llvm.store %552, %554 : i64, !llvm.ptr
cf.br ^bb87
^bb87:
%555 = llvm.load %554 : !llvm.ptr -> i64
%556 = llvm.load %505 : !llvm.ptr -> i64
%557 = arith.cmpi slt, %555, %556 : i64
cf.cond_br %557, ^bb88, ^bb89
^bb88:
%558 = llvm.load %542 : !llvm.ptr -> i64
%559 = llvm.load %554 : !llvm.ptr -> i64
%560 = arith.shrsi %558, %559 : i64
%561 = arith.constant 1 : i32
%563 = arith.extsi %561 : i32 to i64
%562 = arith.andi %560, %563 : i64
%564 = arith.constant 1 : i32
%566 = arith.extsi %564 : i32 to i64
%565 = arith.cmpi eq, %562, %566 : i64
cf.cond_br %565, ^bb90, ^bb91
^bb90:
%567 = llvm.load %550 : !llvm.ptr -> i64
%568 = arith.constant 1 : i32
%570 = llvm.load %554 : !llvm.ptr -> i64
%571 = llvm.getelementptr %497[%570] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%569 = llvm.load %571 : !llvm.ptr -> i64
%573 = arith.extsi %568 : i32 to i64
%572 = arith.shli %573, %569 : i64
%574 = arith.ori %567, %572 : i64
llvm.store %574, %550 : i64, !llvm.ptr
cf.br ^bb92
^bb91:
cf.br ^bb92
^bb92:
%575 = llvm.load %554 : !llvm.ptr -> i64
%576 = arith.constant 1 : i32
%578 = arith.extsi %576 : i32 to i64
%577 = arith.addi %575, %578 : i64
llvm.store %577, %554 : i64, !llvm.ptr
cf.br ^bb87
^bb89:
%579 = llvm.load %550 : !llvm.ptr -> i64
%580 = llvm.load %542 : !llvm.ptr -> i64
%581 = llvm.getelementptr %532[%580] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %579, %581 : i64, !llvm.ptr
%582 = llvm.load %542 : !llvm.ptr -> i64
%583 = arith.constant 1 : i32
%585 = arith.extsi %583 : i32 to i64
%584 = arith.addi %582, %585 : i64
llvm.store %584, %542 : i64, !llvm.ptr
cf.br ^bb84
^bb86:
%586 = arith.constant 0 : i32
%587 = arith.extsi %586 : i32 to i64
%588 = llvm.mlir.constant(1 : i64) : i64
%589 = llvm.alloca %588 x i64 : (i64) -> !llvm.ptr
llvm.store %587, %589 : i64, !llvm.ptr
%590 = arith.constant 0 : i32
%591 = arith.extsi %590 : i32 to i64
%592 = llvm.mlir.constant(1 : i64) : i64
%593 = llvm.alloca %592 x i64 : (i64) -> !llvm.ptr
llvm.store %591, %593 : i64, !llvm.ptr
cf.br ^bb93
^bb93:
%594 = llvm.load %593 : !llvm.ptr -> i64
%595 = llvm.load %387 : !llvm.ptr -> i64
%596 = arith.cmpi slt, %594, %595 : i64
cf.cond_br %596, ^bb94, ^bb95
^bb94:
%598 = llvm.load %377 : !llvm.ptr -> !llvm.ptr
%599 = llvm.load %593 : !llvm.ptr -> i64
%600 = llvm.getelementptr %598[%599] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%597 = llvm.load %600 : !llvm.ptr -> i64
%601 = arith.cmpi slt, %597, %arg0 : i64
cf.cond_br %601, ^bb96, ^bb97
^bb96:
%602 = arith.constant 1 : i32
%604 = arith.extsi %602 : i32 to i64
%603 = arith.subi %arg0, %604 : i64
%605 = arith.subi %603, %597 : i64
%606 = arith.divsi %605, %458 : i64
%607 = arith.constant 0 : i32
%609 = arith.extsi %607 : i32 to i64
%608 = arith.cmpi sge, %606, %609 : i64
cf.cond_br %608, ^bb99, ^bb100
^bb99:
%610 = arith.constant 1 : i32
%612 = arith.extsi %610 : i32 to i64
%611 = arith.subi %489, %612 : i64
%613 = arith.andi %597, %611 : i64
%614 = arith.constant 0 : i32
%615 = arith.extsi %614 : i32 to i64
llvm.store %615, %542 : i64, !llvm.ptr
cf.br ^bb102
^bb102:
%616 = llvm.load %542 : !llvm.ptr -> i64
%617 = arith.constant 1 : i32
%618 = llvm.load %505 : !llvm.ptr -> i64
%620 = arith.extsi %617 : i32 to i64
%619 = arith.shli %620, %618 : i64
%621 = arith.cmpi slt, %616, %619 : i64
cf.cond_br %621, ^bb103, ^bb104
^bb103:
%623 = llvm.load %542 : !llvm.ptr -> i64
%624 = llvm.getelementptr %532[%623] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%622 = llvm.load %624 : !llvm.ptr -> i64
%625 = arith.subi %622, %613 : i64
%626 = arith.muli %625, %491 : i64
%627 = arith.constant 1 : i32
%629 = arith.extsi %627 : i32 to i64
%628 = arith.subi %489, %629 : i64
%630 = arith.andi %626, %628 : i64
%631 = arith.cmpi sle, %630, %606 : i64
cf.cond_br %631, ^bb105, ^bb106
^bb105:
%632 = arith.muli %458, %630 : i64
%633 = arith.addi %597, %632 : i64
%634 = arith.cmpi slt, %633, %arg0 : i64
%635 = scf.if %634 -> (i1) {
%636 = arith.andi %633, %arg1 : i64
%637 = arith.cmpi eq, %636, %arg1 : i64
scf.yield %637 : i1
} else {
%638 = arith.constant false
scf.yield %638 : i1
}
cf.cond_br %635, ^bb108, ^bb109
^bb108:
%639 = llvm.load %589 : !llvm.ptr -> i64
%640 = arith.constant 1 : i32
%642 = arith.extsi %640 : i32 to i64
%641 = arith.addi %639, %642 : i64
llvm.store %641, %589 : i64, !llvm.ptr
cf.br ^bb110
^bb109:
cf.br ^bb110
^bb110:
cf.br ^bb107
^bb106:
cf.br ^bb107
^bb107:
%643 = llvm.load %542 : !llvm.ptr -> i64
%644 = arith.constant 1 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.addi %643, %646 : i64
llvm.store %645, %542 : i64, !llvm.ptr
cf.br ^bb102
^bb104:
cf.br ^bb101
^bb100:
cf.br ^bb101
^bb101:
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%647 = llvm.load %593 : !llvm.ptr -> i64
%648 = arith.constant 1 : i32
%650 = arith.extsi %648 : i32 to i64
%649 = arith.addi %647, %650 : i64
llvm.store %649, %593 : i64, !llvm.ptr
cf.br ^bb93
^bb95:
func.call @free(%363) : (!llvm.ptr) -> ()
%653 = llvm.load %377 : !llvm.ptr -> !llvm.ptr
func.call @free(%653) : (!llvm.ptr) -> ()
func.call @free(%497) : (!llvm.ptr) -> ()
func.call @free(%532) : (!llvm.ptr) -> ()
%656 = llvm.load %589 : !llvm.ptr -> i64
func.return %656 : i64
}
func.func @T(%arg0: i64, %arg1: i64) -> i64 {
%657 = arith.cmpi sle, %arg0, %arg1 : i64
cf.cond_br %657, ^bb111, ^bb112
^bb111:
%658 = arith.constant 0 : i32
%659 = arith.extsi %658 : i32 to i64
func.return %659 : i64
^bb112:
cf.br ^bb113
^bb113:
%660 = arith.subi %arg0, %arg1 : i64
%661 = func.call @count_supermask_lt(%arg0, %arg1) : (i64, i64) -> i64
%663 = arith.constant 5 : i32
%664 = arith.extsi %663 : i32 to i64
%662 = func.call @count_lucas_not_div_lt(%arg0, %arg1, %664) : (i64, i64, i64) -> i64
%665 = func.call @count_not_div10_lt(%arg0, %arg1) : (i64, i64) -> i64
%666 = arith.subi %660, %661 : i64
%667 = arith.subi %666, %662 : i64
%668 = arith.addi %667, %665 : i64
func.return %668 : i64
}
func.func @main() -> i32 {
%669 = llvm.mlir.addressof @str_0 : !llvm.ptr
%671 = arith.constant 999999995705032704 : i32
%672 = arith.constant 995705032704 : i32
%673 = arith.constant 10 : i32
%674 = arith.subi %672, %673 : i32
%675 = arith.extsi %671 : i32 to i64
%676 = arith.extsi %674 : i32 to i64
%670 = func.call @T(%675, %676) : (i64, i64) -> i64
%677 = llvm.call @printf(%669, %670) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%678 = arith.constant 0 : i32
func.return %678 : i32
}
}