← All problems Problem 944
Sum of Elevisors — S(10^14) mod 1234567891 via O(sqrt n) modular sum.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n)O(log n)Space complexity O(n)O(1)Approach Flow solution Modular exponentiation Verdict Suboptimal
Flow source
# Project Euler 944
# Sum of Elevisors — S(10^14) mod 1234567891 via O(sqrt n) modular sum.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
function sqrt(x: f64) -> f64
}
const MOD: i64 = 1234567891
function modpow(base0: i64, exp0: i64) -> i64 {
let mut r: i64 = 1
let mut b: i64 = base0 % MOD
let mut e: i64 = exp0
while e > 0 {
if (e & 1) != 0 {
r = ((r as i128) * (b as i128) % (MOD as i128)) as i64
}
b = ((b as i128) * (b as i128) % (MOD as i128)) as i64
e = e >> 1
}
return r
}
function sum_range_mod(l: i64, r: i64) -> i64 {
let mut cnt: i64 = r - l + 1
let mut a: i64 = l + r
if (a & 1) == 0 {
a = a / 2
} else {
cnt = cnt / 2
}
return ((a % MOD) as i128 * (cnt % MOD) as i128 % (MOD as i128)) as i64
}
function isqrt(n: i64) -> i64 {
let mut B: i64 = (sqrt(n as f64)) as i64
while (B + 1) * (B + 1) <= n { B = B + 1 }
while B * B > n { B = B - 1 }
return B
}
function S(n: i64) -> i64 {
if n <= 0 { return 0 }
let inv2: i64 = modpow(2, MOD - 2)
let two: i64 = 2
let pow2_n: i64 = modpow(2, n)
let pow2_n_minus1: i64 = ((pow2_n as i128) * (inv2 as i128) % (MOD as i128)) as i64
let mut half_nnp1: i64 = 0
if (n & 1) == 0 {
half_nnp1 = ((n / 2) % MOD) * ((n + 1) % MOD) % MOD
} else {
half_nnp1 = (n % MOD) * (((n + 1) / 2) % MOD) % MOD
}
let first_term: i64 = ((pow2_n_minus1 as i128) * (half_nnp1 as i128) % (MOD as i128)) as i64
let B: i64 = isqrt(n)
let L: i64 = 200000
let mut pow2_small: ptr<i64> = calloc(L + 1, 8)
pow2_small[0] = 1
for i in 1..(L + 1) {
pow2_small[i] = (pow2_small[i - 1] * 2) % MOD
}
let mut U_small: i64 = 0
let mut q: i64 = n
let mut a: i64 = modpow(inv2, q)
let mut x: i64 = 1
while x <= B {
U_small = (U_small + ((x % MOD) as i128 * (a as i128) % (MOD as i128)) as i64) % MOD
if x == B { break }
let next_q: i64 = n / (x + 1)
let delta: i64 = q - next_q
if delta <= L {
a = ((a as i128) * (pow2_small[delta] as i128) % (MOD as i128)) as i64
} else {
a = ((a as i128) * (modpow(2, delta) as i128) % (MOD as i128)) as i64
}
q = next_q
x = x + 1
}
let mut U_large: i64 = 0
let mut prev_r: i64 = n / (B + 1)
let mut weight: i64 = modpow(inv2, B)
let mut qq: i64 = B
while qq >= 1 {
let r: i64 = n / qq
let mut l: i64 = prev_r + 1
prev_r = r
if r <= B {
weight = (weight * two) % MOD
qq = qq - 1
continue
}
if l <= B { l = B + 1 }
if l <= r {
let sum_x: i64 = sum_range_mod(l, r)
U_large = (U_large + ((sum_x as i128) * (weight as i128) % (MOD as i128)) as i64) % MOD
}
weight = (weight * two) % MOD
qq = qq - 1
}
let U: i64 = (U_small + U_large) % MOD
let second_term: i64 = ((pow2_n as i128) * (U as i128) % (MOD as i128)) as i64
free(pow2_small)
let mut ans: i64 = (first_term - second_term) % MOD
if ans < 0 { ans = ans + MOD }
return ans
}
function main() -> i32 {
printf("%lld\n", S(100000000000000))
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(int64_t base0, int64_t exp0);
int64_t sum_range_mod_i64_i64(int64_t l, int64_t r);
int64_t isqrt_i64(int64_t n);
int64_t S_i64(int64_t n);
int32_t main(void);
static const int64_t MOD = 1234567891;
int64_t modpow_i64_i64(int64_t base0, int64_t exp0) {
int64_t r = 1;
int64_t b = FLOW_CHECKED_MOD((base0), (MOD));
int64_t e = exp0;
while (e > 0) {
if ((e & 1) != 0) {
r = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(r)) * ((__int128)(b)))), (((__int128)(MOD))))));
}
b = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(b)) * ((__int128)(b)))), (((__int128)(MOD))))));
e = FLOW_CHECKED_SHR((e), (1));
}
return r;
}
int64_t sum_range_mod_i64_i64(int64_t l, int64_t r) {
int64_t cnt = ((r - l) + 1);
int64_t a = (l + r);
if ((a & 1) == 0) {
a = FLOW_CHECKED_DIV((a), (2));
} else {
cnt = FLOW_CHECKED_DIV((cnt), (2));
}
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD((a), (MOD)))) * ((__int128)(FLOW_CHECKED_MOD((cnt), (MOD)))))), (((__int128)(MOD))))));
}
int64_t isqrt_i64(int64_t n) {
int64_t B = ((int64_t)(sqrt(((double)(n)))));
while (((B + 1) * (B + 1)) <= n) {
B = (B + 1);
}
while ((B * B) > n) {
B = (B - 1);
}
return B;
}
int64_t S_i64(int64_t n) {
if (n <= 0) {
return 0;
}
int64_t inv2 = modpow_i64_i64(2, (MOD - 2));
int64_t two = 2;
int64_t pow2_n = modpow_i64_i64(2, n);
int64_t pow2_n_minus1 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(pow2_n)) * ((__int128)(inv2)))), (((__int128)(MOD))))));
int64_t half_nnp1 = 0;
if ((n & 1) == 0) {
half_nnp1 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((n), (2))), (MOD)) * FLOW_CHECKED_MOD(((n + 1)), (MOD)))), (MOD));
} else {
half_nnp1 = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((n), (MOD)) * FLOW_CHECKED_MOD((FLOW_CHECKED_DIV(((n + 1)), (2))), (MOD)))), (MOD));
}
int64_t first_term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(pow2_n_minus1)) * ((__int128)(half_nnp1)))), (((__int128)(MOD))))));
int64_t B = isqrt_i64(n);
int64_t L = 200000;
int64_t* pow2_small = (int64_t*)(calloc((L + 1), 8));
pow2_small[0] = 1;
int32_t __flow_step_1 = 1;
for (int32_t i = 1; (1 <= (L + 1)) ? i < (L + 1) : i > (L + 1); i += (1 <= (L + 1)) ? 1 : -1) {
pow2_small[i] = FLOW_CHECKED_MOD(((pow2_small[(i - 1)] * 2)), (MOD));
}
int64_t U_small = 0;
int64_t q = n;
int64_t a = modpow_i64_i64(inv2, q);
int64_t x = 1;
while (x <= B) {
U_small = FLOW_CHECKED_MOD(((U_small + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD((x), (MOD)))) * ((__int128)(a)))), (((__int128)(MOD)))))))), (MOD));
if (x == B) {
break;
}
int64_t next_q = FLOW_CHECKED_DIV((n), ((x + 1)));
int64_t delta = (q - next_q);
if (delta <= L) {
a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(pow2_small[delta])))), (((__int128)(MOD))))));
} else {
a = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(modpow_i64_i64(2, delta))))), (((__int128)(MOD))))));
}
q = next_q;
x = (x + 1);
}
int64_t U_large = 0;
int64_t prev_r = FLOW_CHECKED_DIV((n), ((B + 1)));
int64_t weight = modpow_i64_i64(inv2, B);
int64_t qq = B;
while (qq >= 1) {
int64_t r = FLOW_CHECKED_DIV((n), (qq));
int64_t l = (prev_r + 1);
prev_r = r;
if (r <= B) {
weight = FLOW_CHECKED_MOD(((weight * two)), (MOD));
qq = (qq - 1);
continue;
}
if (l <= B) {
l = (B + 1);
}
if (l <= r) {
int64_t sum_x = sum_range_mod_i64_i64(l, r);
U_large = FLOW_CHECKED_MOD(((U_large + ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(sum_x)) * ((__int128)(weight)))), (((__int128)(MOD)))))))), (MOD));
}
weight = FLOW_CHECKED_MOD(((weight * two)), (MOD));
qq = (qq - 1);
}
int64_t U = FLOW_CHECKED_MOD(((U_small + U_large)), (MOD));
int64_t second_term = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(pow2_n)) * ((__int128)(U)))), (((__int128)(MOD))))));
free(pow2_small);
int64_t ans = FLOW_CHECKED_MOD(((first_term - second_term)), (MOD));
if (ans < 0) {
ans = (ans + MOD);
}
return ans;
}
int32_t main(void) {
printf("%lld\n", S_i64(100000000000000));
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 private @sqrt(f64) -> f64
// Constant: MOD
llvm.mlir.global internal constant @MOD(1234567891 : i64) : i64
func.func @modpow(%arg0: i64, %arg1: 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 = llvm.mlir.addressof @MOD : !llvm.ptr
%5 = llvm.load %4 : !llvm.ptr -> i64
%6 = arith.remsi %arg0, %5 : i64
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %6, %8 : i64, !llvm.ptr
%9 = llvm.mlir.constant(1 : i64) : i64
%10 = llvm.alloca %9 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %10 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%11 = llvm.load %10 : !llvm.ptr -> i64
%12 = arith.constant 0 : i32
%14 = arith.extsi %12 : i32 to i64
%13 = arith.cmpi sgt, %11, %14 : i64
cf.cond_br %13, ^bb1, ^bb2
^bb1:
%15 = llvm.load %10 : !llvm.ptr -> i64
%16 = arith.constant 1 : i32
%18 = arith.extsi %16 : i32 to i64
%17 = arith.andi %15, %18 : i64
%19 = arith.constant 0 : i32
%21 = arith.extsi %19 : i32 to i64
%20 = arith.cmpi ne, %17, %21 : i64
cf.cond_br %20, ^bb3, ^bb4
^bb3:
%22 = llvm.load %3 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%24 = llvm.load %8 : !llvm.ptr -> i64
%25 = arith.extsi %24 : i64 to i128
%27 = arith.trunci %23 : i128 to i64
%28 = arith.trunci %25 : i128 to i64
%26 = arith.muli %27, %28 : i64
%29 = llvm.mlir.addressof @MOD : !llvm.ptr
%30 = llvm.load %29 : !llvm.ptr -> i64
%31 = arith.extsi %30 : i64 to i128
%33 = arith.trunci %31 : i128 to i64
%32 = arith.remsi %26, %33 : i64
llvm.store %32, %3 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%34 = llvm.load %8 : !llvm.ptr -> i64
%35 = arith.extsi %34 : i64 to i128
%36 = llvm.load %8 : !llvm.ptr -> i64
%37 = arith.extsi %36 : i64 to i128
%39 = arith.trunci %35 : i128 to i64
%40 = arith.trunci %37 : i128 to i64
%38 = arith.muli %39, %40 : i64
%41 = llvm.mlir.addressof @MOD : !llvm.ptr
%42 = llvm.load %41 : !llvm.ptr -> i64
%43 = arith.extsi %42 : i64 to i128
%45 = arith.trunci %43 : i128 to i64
%44 = arith.remsi %38, %45 : i64
llvm.store %44, %8 : i64, !llvm.ptr
%46 = llvm.load %10 : !llvm.ptr -> i64
%47 = arith.constant 1 : i32
%49 = arith.extsi %47 : i32 to i64
%48 = arith.shrsi %46, %49 : i64
llvm.store %48, %10 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%50 = llvm.load %3 : !llvm.ptr -> i64
func.return %50 : i64
}
func.func @sum_range_mod(%arg0: i64, %arg1: i64) -> i64 {
%51 = arith.subi %arg1, %arg0 : i64
%52 = arith.constant 1 : i32
%54 = arith.extsi %52 : i32 to i64
%53 = arith.addi %51, %54 : i64
%55 = llvm.mlir.constant(1 : i64) : i64
%56 = llvm.alloca %55 x i64 : (i64) -> !llvm.ptr
llvm.store %53, %56 : i64, !llvm.ptr
%57 = arith.addi %arg0, %arg1 : i64
%58 = llvm.mlir.constant(1 : i64) : i64
%59 = llvm.alloca %58 x i64 : (i64) -> !llvm.ptr
llvm.store %57, %59 : i64, !llvm.ptr
%60 = llvm.load %59 : !llvm.ptr -> i64
%61 = arith.constant 1 : i32
%63 = arith.extsi %61 : i32 to i64
%62 = arith.andi %60, %63 : i64
%64 = arith.constant 0 : i32
%66 = arith.extsi %64 : i32 to i64
%65 = arith.cmpi eq, %62, %66 : i64
cf.cond_br %65, ^bb6, ^bb7
^bb6:
%67 = llvm.load %59 : !llvm.ptr -> i64
%68 = arith.constant 2 : i32
%70 = arith.extsi %68 : i32 to i64
%69 = arith.divsi %67, %70 : i64
llvm.store %69, %59 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
%71 = llvm.load %56 : !llvm.ptr -> i64
%72 = arith.constant 2 : i32
%74 = arith.extsi %72 : i32 to i64
%73 = arith.divsi %71, %74 : i64
llvm.store %73, %56 : i64, !llvm.ptr
cf.br ^bb8
^bb8:
%75 = llvm.load %59 : !llvm.ptr -> i64
%76 = llvm.mlir.addressof @MOD : !llvm.ptr
%77 = llvm.load %76 : !llvm.ptr -> i64
%78 = arith.remsi %75, %77 : i64
%79 = arith.extsi %78 : i64 to i128
%80 = llvm.load %56 : !llvm.ptr -> i64
%81 = llvm.mlir.addressof @MOD : !llvm.ptr
%82 = llvm.load %81 : !llvm.ptr -> i64
%83 = arith.remsi %80, %82 : i64
%84 = arith.extsi %83 : i64 to i128
%86 = arith.trunci %79 : i128 to i64
%87 = arith.trunci %84 : i128 to i64
%85 = arith.muli %86, %87 : i64
%88 = llvm.mlir.addressof @MOD : !llvm.ptr
%89 = llvm.load %88 : !llvm.ptr -> i64
%90 = arith.extsi %89 : i64 to i128
%92 = arith.trunci %90 : i128 to i64
%91 = arith.remsi %85, %92 : i64
func.return %91 : i64
}
func.func @isqrt(%arg0: i64) -> i64 {
%93 = arith.sitofp %arg0 : i64 to f64
%94 = math.sqrt %93 : f64
%95 = arith.fptosi %94 : f64 to i64
%96 = llvm.mlir.constant(1 : i64) : i64
%97 = llvm.alloca %96 x i64 : (i64) -> !llvm.ptr
llvm.store %95, %97 : i64, !llvm.ptr
cf.br ^bb9
^bb9:
%98 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.constant 1 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.addi %98, %101 : i64
%102 = llvm.load %97 : !llvm.ptr -> i64
%103 = arith.constant 1 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.addi %102, %105 : i64
%106 = arith.muli %100, %104 : i64
%107 = arith.cmpi sle, %106, %arg0 : i64
cf.cond_br %107, ^bb10, ^bb11
^bb10:
%108 = llvm.load %97 : !llvm.ptr -> i64
%109 = arith.constant 1 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.addi %108, %111 : i64
llvm.store %110, %97 : i64, !llvm.ptr
cf.br ^bb9
^bb11:
cf.br ^bb12
^bb12:
%112 = llvm.load %97 : !llvm.ptr -> i64
%113 = llvm.load %97 : !llvm.ptr -> i64
%114 = arith.muli %112, %113 : i64
%115 = arith.cmpi sgt, %114, %arg0 : i64
cf.cond_br %115, ^bb13, ^bb14
^bb13:
%116 = llvm.load %97 : !llvm.ptr -> i64
%117 = arith.constant 1 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.subi %116, %119 : i64
llvm.store %118, %97 : i64, !llvm.ptr
cf.br ^bb12
^bb14:
%120 = llvm.load %97 : !llvm.ptr -> i64
func.return %120 : i64
}
func.func @S(%arg0: i64) -> i64 {
%121 = arith.constant 0 : i32
%123 = arith.extsi %121 : i32 to i64
%122 = arith.cmpi sle, %arg0, %123 : i64
cf.cond_br %122, ^bb15, ^bb16
^bb15:
%124 = arith.constant 0 : i32
%125 = arith.extsi %124 : i32 to i64
func.return %125 : i64
^bb16:
cf.br ^bb17
^bb17:
%127 = arith.constant 2 : i32
%128 = llvm.mlir.addressof @MOD : !llvm.ptr
%129 = llvm.load %128 : !llvm.ptr -> i64
%130 = arith.constant 2 : i32
%132 = arith.extsi %130 : i32 to i64
%131 = arith.subi %129, %132 : i64
%133 = arith.extsi %127 : i32 to i64
%126 = func.call @modpow(%133, %131) : (i64, i64) -> i64
%134 = arith.constant 2 : i32
%135 = arith.extsi %134 : i32 to i64
%137 = arith.constant 2 : i32
%138 = arith.extsi %137 : i32 to i64
%136 = func.call @modpow(%138, %arg0) : (i64, i64) -> i64
%139 = arith.extsi %136 : i64 to i128
%140 = arith.extsi %126 : i64 to i128
%142 = arith.trunci %139 : i128 to i64
%143 = arith.trunci %140 : i128 to i64
%141 = arith.muli %142, %143 : i64
%144 = llvm.mlir.addressof @MOD : !llvm.ptr
%145 = llvm.load %144 : !llvm.ptr -> i64
%146 = arith.extsi %145 : i64 to i128
%148 = arith.trunci %146 : i128 to i64
%147 = arith.remsi %141, %148 : i64
%149 = arith.constant 0 : i32
%150 = arith.extsi %149 : i32 to i64
%151 = llvm.mlir.constant(1 : i64) : i64
%152 = llvm.alloca %151 x i64 : (i64) -> !llvm.ptr
llvm.store %150, %152 : i64, !llvm.ptr
%153 = arith.constant 1 : i32
%155 = arith.extsi %153 : i32 to i64
%154 = arith.andi %arg0, %155 : i64
%156 = arith.constant 0 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.cmpi eq, %154, %158 : i64
cf.cond_br %157, ^bb18, ^bb19
^bb18:
%159 = arith.constant 2 : i32
%161 = arith.extsi %159 : i32 to i64
%160 = arith.divsi %arg0, %161 : i64
%162 = llvm.mlir.addressof @MOD : !llvm.ptr
%163 = llvm.load %162 : !llvm.ptr -> i64
%164 = arith.remsi %160, %163 : i64
%165 = arith.constant 1 : i32
%167 = arith.extsi %165 : i32 to i64
%166 = arith.addi %arg0, %167 : i64
%168 = llvm.mlir.addressof @MOD : !llvm.ptr
%169 = llvm.load %168 : !llvm.ptr -> i64
%170 = arith.remsi %166, %169 : i64
%171 = arith.muli %164, %170 : i64
%172 = llvm.mlir.addressof @MOD : !llvm.ptr
%173 = llvm.load %172 : !llvm.ptr -> i64
%174 = arith.remsi %171, %173 : i64
llvm.store %174, %152 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
%175 = llvm.mlir.addressof @MOD : !llvm.ptr
%176 = llvm.load %175 : !llvm.ptr -> i64
%177 = arith.remsi %arg0, %176 : i64
%178 = arith.constant 1 : i32
%180 = arith.extsi %178 : i32 to i64
%179 = arith.addi %arg0, %180 : i64
%181 = arith.constant 2 : i32
%183 = arith.extsi %181 : i32 to i64
%182 = arith.divsi %179, %183 : i64
%184 = llvm.mlir.addressof @MOD : !llvm.ptr
%185 = llvm.load %184 : !llvm.ptr -> i64
%186 = arith.remsi %182, %185 : i64
%187 = arith.muli %177, %186 : i64
%188 = llvm.mlir.addressof @MOD : !llvm.ptr
%189 = llvm.load %188 : !llvm.ptr -> i64
%190 = arith.remsi %187, %189 : i64
llvm.store %190, %152 : i64, !llvm.ptr
cf.br ^bb20
^bb20:
%191 = arith.extsi %147 : i64 to i128
%192 = llvm.load %152 : !llvm.ptr -> i64
%193 = arith.extsi %192 : i64 to i128
%195 = arith.trunci %191 : i128 to i64
%196 = arith.trunci %193 : i128 to i64
%194 = arith.muli %195, %196 : i64
%197 = llvm.mlir.addressof @MOD : !llvm.ptr
%198 = llvm.load %197 : !llvm.ptr -> i64
%199 = arith.extsi %198 : i64 to i128
%201 = arith.trunci %199 : i128 to i64
%200 = arith.remsi %194, %201 : i64
%202 = func.call @isqrt(%arg0) : (i64) -> i64
%203 = arith.constant 200000 : i32
%204 = arith.extsi %203 : i32 to i64
%206 = arith.constant 1 : i32
%208 = arith.extsi %206 : i32 to i64
%207 = arith.addi %204, %208 : i64
%209 = arith.constant 8 : i32
%210 = arith.extsi %209 : i32 to i64
%205 = func.call @calloc(%207, %210) : (i64, i64) -> !llvm.ptr
%211 = llvm.mlir.constant(1 : i64) : i64
%212 = llvm.alloca %211 x !llvm.ptr : (i64) -> !llvm.ptr
llvm.store %205, %212 : !llvm.ptr, !llvm.ptr
%213 = arith.constant 1 : i32
%214 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
%215 = arith.constant 0 : i32
%216 = arith.extsi %213 : i32 to i64
%217 = arith.extsi %215 : i32 to i64
%218 = llvm.getelementptr %214[%217] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %216, %218 : i64, !llvm.ptr
%219 = arith.constant 1 : i32
%220 = arith.constant 1 : i32
%222 = arith.extsi %220 : i32 to i64
%221 = arith.addi %204, %222 : i64
%223 = arith.index_cast %219 : i32 to index
%224 = arith.index_cast %221 : i32 to index
%226 = arith.constant 1 : index
%227 = arith.constant -1 : index
%228 = arith.cmpi sle, %223, %224 : index
%225 = arith.select %228, %226, %227 : index
cf.br ^bb21(%223 : index)
^bb21(%229: index):
%230 = arith.cmpi slt, %229, %224 : index
%231 = arith.cmpi sgt, %229, %224 : index
%232 = arith.select %228, %230, %231 : i1
cf.cond_br %232, ^bb22(%229 : index), ^bb23(%229 : index)
^bb22(%233: index):
%235 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
%236 = arith.constant 1 : i32
%238 = arith.index_cast %233 : index to i32
%237 = arith.subi %238, %236 : i32
%239 = arith.extsi %237 : i32 to i64
%240 = llvm.getelementptr %235[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%234 = llvm.load %240 : !llvm.ptr -> i64
%241 = arith.constant 2 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.muli %234, %243 : i64
%244 = llvm.mlir.addressof @MOD : !llvm.ptr
%245 = llvm.load %244 : !llvm.ptr -> i64
%246 = arith.remsi %242, %245 : i64
%247 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
%248 = arith.index_cast %233 : index to i64
%249 = llvm.getelementptr %247[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %246, %249 : i64, !llvm.ptr
%250 = arith.addi %233, %225 : index
cf.br ^bb21(%250 : index)
^bb23(%251: index):
%252 = arith.constant 0 : i32
%253 = arith.extsi %252 : i32 to i64
%254 = llvm.mlir.constant(1 : i64) : i64
%255 = llvm.alloca %254 x i64 : (i64) -> !llvm.ptr
llvm.store %253, %255 : i64, !llvm.ptr
%256 = llvm.mlir.constant(1 : i64) : i64
%257 = llvm.alloca %256 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %257 : i64, !llvm.ptr
%259 = llvm.load %257 : !llvm.ptr -> i64
%258 = func.call @modpow(%126, %259) : (i64, i64) -> i64
%260 = llvm.mlir.constant(1 : i64) : i64
%261 = llvm.alloca %260 x i64 : (i64) -> !llvm.ptr
llvm.store %258, %261 : i64, !llvm.ptr
%262 = arith.constant 1 : i32
%263 = arith.extsi %262 : i32 to i64
%264 = llvm.mlir.constant(1 : i64) : i64
%265 = llvm.alloca %264 x i64 : (i64) -> !llvm.ptr
llvm.store %263, %265 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%266 = llvm.load %265 : !llvm.ptr -> i64
%267 = arith.cmpi sle, %266, %202 : i64
cf.cond_br %267, ^bb25, ^bb26
^bb25:
%268 = llvm.load %255 : !llvm.ptr -> i64
%269 = llvm.load %265 : !llvm.ptr -> i64
%270 = llvm.mlir.addressof @MOD : !llvm.ptr
%271 = llvm.load %270 : !llvm.ptr -> i64
%272 = arith.remsi %269, %271 : i64
%273 = arith.extsi %272 : i64 to i128
%274 = llvm.load %261 : !llvm.ptr -> i64
%275 = arith.extsi %274 : i64 to i128
%277 = arith.trunci %273 : i128 to i64
%278 = arith.trunci %275 : i128 to i64
%276 = arith.muli %277, %278 : i64
%279 = llvm.mlir.addressof @MOD : !llvm.ptr
%280 = llvm.load %279 : !llvm.ptr -> i64
%281 = arith.extsi %280 : i64 to i128
%283 = arith.trunci %281 : i128 to i64
%282 = arith.remsi %276, %283 : i64
%284 = arith.addi %268, %282 : i64
%285 = llvm.mlir.addressof @MOD : !llvm.ptr
%286 = llvm.load %285 : !llvm.ptr -> i64
%287 = arith.remsi %284, %286 : i64
llvm.store %287, %255 : i64, !llvm.ptr
%288 = llvm.load %265 : !llvm.ptr -> i64
%289 = arith.cmpi eq, %288, %202 : i64
cf.cond_br %289, ^bb27, ^bb28
^bb27:
cf.br ^bb26
^bb28:
cf.br ^bb29
^bb29:
%290 = llvm.load %265 : !llvm.ptr -> i64
%291 = arith.constant 1 : i32
%293 = arith.extsi %291 : i32 to i64
%292 = arith.addi %290, %293 : i64
%294 = arith.divsi %arg0, %292 : i64
%295 = llvm.load %257 : !llvm.ptr -> i64
%296 = arith.subi %295, %294 : i64
%297 = arith.cmpi sle, %296, %204 : i64
cf.cond_br %297, ^bb30, ^bb31
^bb30:
%298 = llvm.load %261 : !llvm.ptr -> i64
%299 = arith.extsi %298 : i64 to i128
%301 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
%302 = llvm.getelementptr %301[%296] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%300 = llvm.load %302 : !llvm.ptr -> i64
%303 = arith.extsi %300 : i64 to i128
%305 = arith.trunci %299 : i128 to i64
%306 = arith.trunci %303 : i128 to i64
%304 = arith.muli %305, %306 : i64
%307 = llvm.mlir.addressof @MOD : !llvm.ptr
%308 = llvm.load %307 : !llvm.ptr -> i64
%309 = arith.extsi %308 : i64 to i128
%311 = arith.trunci %309 : i128 to i64
%310 = arith.remsi %304, %311 : i64
llvm.store %310, %261 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
%312 = llvm.load %261 : !llvm.ptr -> i64
%313 = arith.extsi %312 : i64 to i128
%315 = arith.constant 2 : i32
%316 = arith.extsi %315 : i32 to i64
%314 = func.call @modpow(%316, %296) : (i64, i64) -> i64
%317 = arith.extsi %314 : i64 to i128
%319 = arith.trunci %313 : i128 to i64
%320 = arith.trunci %317 : i128 to i64
%318 = arith.muli %319, %320 : i64
%321 = llvm.mlir.addressof @MOD : !llvm.ptr
%322 = llvm.load %321 : !llvm.ptr -> i64
%323 = arith.extsi %322 : i64 to i128
%325 = arith.trunci %323 : i128 to i64
%324 = arith.remsi %318, %325 : i64
llvm.store %324, %261 : i64, !llvm.ptr
cf.br ^bb32
^bb32:
llvm.store %294, %257 : i64, !llvm.ptr
%326 = llvm.load %265 : !llvm.ptr -> i64
%327 = arith.constant 1 : i32
%329 = arith.extsi %327 : i32 to i64
%328 = arith.addi %326, %329 : i64
llvm.store %328, %265 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%330 = arith.constant 0 : i32
%331 = arith.extsi %330 : i32 to i64
%332 = llvm.mlir.constant(1 : i64) : i64
%333 = llvm.alloca %332 x i64 : (i64) -> !llvm.ptr
llvm.store %331, %333 : i64, !llvm.ptr
%334 = arith.constant 1 : i32
%336 = arith.extsi %334 : i32 to i64
%335 = arith.addi %202, %336 : i64
%337 = arith.divsi %arg0, %335 : i64
%338 = llvm.mlir.constant(1 : i64) : i64
%339 = llvm.alloca %338 x i64 : (i64) -> !llvm.ptr
llvm.store %337, %339 : i64, !llvm.ptr
%340 = func.call @modpow(%126, %202) : (i64, i64) -> i64
%341 = llvm.mlir.constant(1 : i64) : i64
%342 = llvm.alloca %341 x i64 : (i64) -> !llvm.ptr
llvm.store %340, %342 : i64, !llvm.ptr
%343 = llvm.mlir.constant(1 : i64) : i64
%344 = llvm.alloca %343 x i64 : (i64) -> !llvm.ptr
llvm.store %202, %344 : i64, !llvm.ptr
cf.br ^bb33
^bb33:
%345 = llvm.load %344 : !llvm.ptr -> i64
%346 = arith.constant 1 : i32
%348 = arith.extsi %346 : i32 to i64
%347 = arith.cmpi sge, %345, %348 : i64
cf.cond_br %347, ^bb34, ^bb35
^bb34:
%349 = llvm.load %344 : !llvm.ptr -> i64
%350 = arith.divsi %arg0, %349 : i64
%351 = llvm.load %339 : !llvm.ptr -> i64
%352 = arith.constant 1 : i32
%354 = arith.extsi %352 : i32 to i64
%353 = arith.addi %351, %354 : i64
%355 = llvm.mlir.constant(1 : i64) : i64
%356 = llvm.alloca %355 x i64 : (i64) -> !llvm.ptr
llvm.store %353, %356 : i64, !llvm.ptr
llvm.store %350, %339 : i64, !llvm.ptr
%357 = arith.cmpi sle, %350, %202 : i64
cf.cond_br %357, ^bb36, ^bb37
^bb36:
%358 = llvm.load %342 : !llvm.ptr -> i64
%359 = arith.muli %358, %135 : i64
%360 = llvm.mlir.addressof @MOD : !llvm.ptr
%361 = llvm.load %360 : !llvm.ptr -> i64
%362 = arith.remsi %359, %361 : i64
llvm.store %362, %342 : i64, !llvm.ptr
%363 = llvm.load %344 : !llvm.ptr -> i64
%364 = arith.constant 1 : i32
%366 = arith.extsi %364 : i32 to i64
%365 = arith.subi %363, %366 : i64
llvm.store %365, %344 : i64, !llvm.ptr
cf.br ^bb33
^bb37:
cf.br ^bb38
^bb38:
%367 = llvm.load %356 : !llvm.ptr -> i64
%368 = arith.cmpi sle, %367, %202 : i64
cf.cond_br %368, ^bb39, ^bb40
^bb39:
%369 = arith.constant 1 : i32
%371 = arith.extsi %369 : i32 to i64
%370 = arith.addi %202, %371 : i64
llvm.store %370, %356 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%372 = llvm.load %356 : !llvm.ptr -> i64
%373 = arith.cmpi sle, %372, %350 : i64
cf.cond_br %373, ^bb42, ^bb43
^bb42:
%375 = llvm.load %356 : !llvm.ptr -> i64
%374 = func.call @sum_range_mod(%375, %350) : (i64, i64) -> i64
%376 = llvm.load %333 : !llvm.ptr -> i64
%377 = arith.extsi %374 : i64 to i128
%378 = llvm.load %342 : !llvm.ptr -> i64
%379 = arith.extsi %378 : i64 to i128
%381 = arith.trunci %377 : i128 to i64
%382 = arith.trunci %379 : i128 to i64
%380 = arith.muli %381, %382 : i64
%383 = llvm.mlir.addressof @MOD : !llvm.ptr
%384 = llvm.load %383 : !llvm.ptr -> i64
%385 = arith.extsi %384 : i64 to i128
%387 = arith.trunci %385 : i128 to i64
%386 = arith.remsi %380, %387 : i64
%388 = arith.addi %376, %386 : i64
%389 = llvm.mlir.addressof @MOD : !llvm.ptr
%390 = llvm.load %389 : !llvm.ptr -> i64
%391 = arith.remsi %388, %390 : i64
llvm.store %391, %333 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
cf.br ^bb44
^bb44:
%392 = llvm.load %342 : !llvm.ptr -> i64
%393 = arith.muli %392, %135 : i64
%394 = llvm.mlir.addressof @MOD : !llvm.ptr
%395 = llvm.load %394 : !llvm.ptr -> i64
%396 = arith.remsi %393, %395 : i64
llvm.store %396, %342 : i64, !llvm.ptr
%397 = llvm.load %344 : !llvm.ptr -> i64
%398 = arith.constant 1 : i32
%400 = arith.extsi %398 : i32 to i64
%399 = arith.subi %397, %400 : i64
llvm.store %399, %344 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
%401 = llvm.load %255 : !llvm.ptr -> i64
%402 = llvm.load %333 : !llvm.ptr -> i64
%403 = arith.addi %401, %402 : i64
%404 = llvm.mlir.addressof @MOD : !llvm.ptr
%405 = llvm.load %404 : !llvm.ptr -> i64
%406 = arith.remsi %403, %405 : i64
%407 = arith.extsi %136 : i64 to i128
%408 = arith.extsi %406 : i64 to i128
%410 = arith.trunci %407 : i128 to i64
%411 = arith.trunci %408 : i128 to i64
%409 = arith.muli %410, %411 : i64
%412 = llvm.mlir.addressof @MOD : !llvm.ptr
%413 = llvm.load %412 : !llvm.ptr -> i64
%414 = arith.extsi %413 : i64 to i128
%416 = arith.trunci %414 : i128 to i64
%415 = arith.remsi %409, %416 : i64
%418 = llvm.load %212 : !llvm.ptr -> !llvm.ptr
func.call @free(%418) : (!llvm.ptr) -> ()
%419 = arith.subi %200, %415 : i64
%420 = llvm.mlir.addressof @MOD : !llvm.ptr
%421 = llvm.load %420 : !llvm.ptr -> i64
%422 = arith.remsi %419, %421 : i64
%423 = llvm.mlir.constant(1 : i64) : i64
%424 = llvm.alloca %423 x i64 : (i64) -> !llvm.ptr
llvm.store %422, %424 : i64, !llvm.ptr
%425 = llvm.load %424 : !llvm.ptr -> i64
%426 = arith.constant 0 : i32
%428 = arith.extsi %426 : i32 to i64
%427 = arith.cmpi slt, %425, %428 : i64
cf.cond_br %427, ^bb45, ^bb46
^bb45:
%429 = llvm.load %424 : !llvm.ptr -> i64
%430 = llvm.mlir.addressof @MOD : !llvm.ptr
%431 = llvm.load %430 : !llvm.ptr -> i64
%432 = arith.addi %429, %431 : i64
llvm.store %432, %424 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%433 = llvm.load %424 : !llvm.ptr -> i64
func.return %433 : i64
}
func.func @main() -> i32 {
%434 = llvm.mlir.addressof @str_0 : !llvm.ptr
%436 = arith.constant 99995705032704 : i32
%437 = arith.extsi %436 : i32 to i64
%435 = func.call @S(%437) : (i64) -> i64
%438 = llvm.call @printf(%434, %435) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%439 = arith.constant 0 : i32
func.return %439 : i32
}
}