← All problems Problem 747
Triangular pizza cutting: Psi(10^8) mod 1e9+7.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(1)O(n^2)Space complexity O(1)O(n)Approach Flow solution Double enumeration Verdict Optimal
Flow source
# Project Euler 747
# Triangular pizza cutting: Psi(10^8) mod 1e9+7.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
function isqrt_i64(n: i64) -> i64 {
if n < 2 {
return n
}
let mut x: i64 = n
let mut y: i64 = (x + 1) / 2
while y < x {
x = y
y = (x + n / x) / 2
}
return x
}
# Closed form for the "easy" prefix sum:
# (m^3 + 15 m^2 - 52 m + 36) / 6 mod MOD (m >= 3)
function easy_prefix(m: i64) -> i64 {
if m < 3 {
return 0
}
let mm: i64 = MOD * 6
let m3: i64 = (((m as i128) * (m as i128) % (mm as i128)) * (m as i128) % (mm as i128)) as i64
let m2: i64 = ((m as i128) * (m as i128) % (mm as i128)) as i64
let num: i64 = (m3 + (15 * m2 % mm) + (mm - 52 * m % mm) + 36) % mm
return num / 6
}
# For fixed (x,y), compute n_min and whether 4D is a perfect square.
# n_min = 2xy + x + y + 1 + ceil(2*sqrt(D)), D = x*y*(x+1)*(y+1).
# ceil(2*sqrt(D)) = ceil(sqrt(4D)). If 4D is a perfect square, sq=1.
function min_n_and_square(x: i64, y: i64, sq: ptr<i32>) -> i64 {
let four_d: i64 = 4 * (x * (x + 1)) * (y * (y + 1))
let r: i64 = isqrt_i64(four_d)
if r * r == four_d {
sq[0] = 1
return 2 * x * y + x + y + 1 + r
}
sq[0] = 0
return 2 * x * y + x + y + 1 + (r + 1)
}
# Binary search for max y >= x with n_min(x,y) <= m.
function y_max_for_x(m: i64, x: i64) -> i64 {
if 4 * x > m - 1 {
return x - 1
}
let mut hi: i64 = (m - 1) / (4 * x) + 2
if hi < x {
hi = x
}
let mut lo: i64 = x
let mut ok: i64 = x - 1
let sq: ptr<i32> = calloc(1, 4)
while lo <= hi {
let mid: i64 = (lo + hi) / 2
let n_min: i64 = min_n_and_square(x, mid, sq)
if n_min <= m {
ok = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
free(sq)
return ok
}
function hard_prefix(m: i64) -> i64 {
if m < 3 {
return 0
}
let k: i64 = (m - 1) / 4
if k <= 0 {
return 0
}
let x_max: i64 = isqrt_i64(k)
let mut total: i64 = 0
let cutoff: i64 = MOD << 20
for x in 1..(x_max + 1) {
let ymax: i64 = y_max_for_x(m, x)
if ymax < x {
continue
}
let A: i64 = x * (x + 1)
let mut y: i64 = x
let mut yy1: i64 = y * (y + 1)
let mut two_xy: i64 = 2 * x * y
while y <= ymax {
let four_d: i64 = (A * yy1) << 2
let r: i64 = isqrt_i64(four_d)
let mut sqv: i32 = 0
if r * r == four_d {
sqv = 1
}
let mut ceil2: i64 = 0
if sqv != 0 {
ceil2 = r
} else {
ceil2 = r + 1
}
let n_min: i64 = two_xy + x + y + 1 + ceil2
if n_min <= m {
let cnt: i64 = 2 * (m - n_min + 1) - (sqv as i64)
let mut add: i64 = cnt
if x != y {
add = cnt << 1
}
total = total + add
if total >= cutoff {
total = total % MOD
}
}
yy1 = yy1 + ((y << 1) + 2)
y = y + 1
two_xy = two_xy + (x << 1)
}
}
return total % MOD
}
function main() -> i32 {
let m: i64 = 100000000
let easy: i64 = easy_prefix(m)
let hard: i64 = hard_prefix(m)
let result: i64 = (easy + 3 * hard) % MOD
printf("%lld\n", result)
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 isqrt_i64_i64(int64_t n);
int64_t easy_prefix_i64(int64_t m);
int64_t min_n_and_square_i64_i64_ptr_i32(int64_t x, int64_t y, int32_t* sq);
int64_t y_max_for_x_i64_i64(int64_t m, int64_t x);
int64_t hard_prefix_i64(int64_t m);
int32_t main(void);
static const int64_t MOD = 1000000007;
int64_t isqrt_i64_i64(int64_t n) {
if (n < 2) {
return n;
}
int64_t x = n;
int64_t y = FLOW_CHECKED_DIV(((x + 1)), (2));
while (y < x) {
x = y;
y = FLOW_CHECKED_DIV(((x + FLOW_CHECKED_DIV((n), (x)))), (2));
}
return x;
}
int64_t easy_prefix_i64(int64_t m) {
if (m < 3) {
return 0;
}
int64_t mm = (MOD * 6);
int64_t m3 = ((int64_t)(FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD(((((__int128)(m)) * ((__int128)(m)))), (((__int128)(mm)))) * ((__int128)(m)))), (((__int128)(mm))))));
int64_t m2 = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(m)) * ((__int128)(m)))), (((__int128)(mm))))));
int64_t num = FLOW_CHECKED_MOD(((((m3 + FLOW_CHECKED_MOD(((15 * m2)), (mm))) + (mm - FLOW_CHECKED_MOD(((52 * m)), (mm)))) + 36)), (mm));
return FLOW_CHECKED_DIV((num), (6));
}
int64_t min_n_and_square_i64_i64_ptr_i32(int64_t x, int64_t y, int32_t* sq) {
int64_t four_d = ((4 * (x * (x + 1))) * (y * (y + 1)));
int64_t r = isqrt_i64_i64(four_d);
if ((r * r) == four_d) {
sq[0] = 1;
return ((((((2 * x) * y) + x) + y) + 1) + r);
}
sq[0] = 0;
return ((((((2 * x) * y) + x) + y) + 1) + (r + 1));
}
int64_t y_max_for_x_i64_i64(int64_t m, int64_t x) {
if ((4 * x) > (m - 1)) {
return (x - 1);
}
int64_t hi = (FLOW_CHECKED_DIV(((m - 1)), ((4 * x))) + 2);
if (hi < x) {
hi = x;
}
int64_t lo = x;
int64_t ok = (x - 1);
int32_t* sq = (int32_t*)(calloc(1, 4));
while (lo <= hi) {
int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
int64_t n_min = min_n_and_square_i64_i64_ptr_i32(x, mid, sq);
if (n_min <= m) {
ok = mid;
lo = (mid + 1);
} else {
hi = (mid - 1);
}
}
free(sq);
return ok;
}
int64_t hard_prefix_i64(int64_t m) {
if (m < 3) {
return 0;
}
int64_t k = FLOW_CHECKED_DIV(((m - 1)), (4));
if (k <= 0) {
return 0;
}
int64_t x_max = isqrt_i64_i64(k);
int64_t total = 0;
int64_t cutoff = FLOW_CHECKED_SHL((MOD), (20));
int32_t __flow_step_1 = 1;
for (int32_t x = 1; (1 <= (x_max + 1)) ? x < (x_max + 1) : x > (x_max + 1); x += (1 <= (x_max + 1)) ? 1 : -1) {
int64_t ymax = y_max_for_x_i64_i64(m, x);
if (ymax < x) {
continue;
}
int64_t A = (x * (x + 1));
int64_t y = x;
int64_t yy1 = (y * (y + 1));
int64_t two_xy = ((2 * x) * y);
while (y <= ymax) {
int64_t four_d = FLOW_CHECKED_SHL(((A * yy1)), (2));
int64_t r = isqrt_i64_i64(four_d);
int32_t sqv = 0;
if ((r * r) == four_d) {
sqv = 1;
}
int64_t ceil2 = 0;
if (sqv != 0) {
ceil2 = r;
} else {
ceil2 = (r + 1);
}
int64_t n_min = ((((two_xy + x) + y) + 1) + ceil2);
if (n_min <= m) {
int64_t cnt = ((2 * ((m - n_min) + 1)) - ((int64_t)(sqv)));
int64_t add = cnt;
if (x != y) {
add = FLOW_CHECKED_SHL((cnt), (1));
}
total = (total + add);
if (total >= cutoff) {
total = FLOW_CHECKED_MOD((total), (MOD));
}
}
yy1 = (yy1 + (FLOW_CHECKED_SHL((y), (1)) + 2));
y = (y + 1);
two_xy = (two_xy + FLOW_CHECKED_SHL((x), (1)));
}
}
return FLOW_CHECKED_MOD((total), (MOD));
}
int32_t main(void) {
int64_t m = 100000000;
int64_t easy = easy_prefix_i64(m);
int64_t hard = hard_prefix_i64(m);
int64_t result = FLOW_CHECKED_MOD(((easy + (3 * hard))), (MOD));
printf("%lld\n", result);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @isqrt_i64(%arg0: i64) -> i64 {
%0 = arith.constant 2 : i32
%2 = arith.extsi %0 : i32 to i64
%1 = arith.cmpi slt, %arg0, %2 : i64
cf.cond_br %1, ^bb0, ^bb1
^bb0:
func.return %arg0 : i64
^bb1:
cf.br ^bb2
^bb2:
%3 = llvm.mlir.constant(1 : i64) : i64
%4 = llvm.alloca %3 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %4 : i64, !llvm.ptr
%5 = llvm.load %4 : !llvm.ptr -> i64
%6 = arith.constant 1 : i32
%8 = arith.extsi %6 : i32 to i64
%7 = arith.addi %5, %8 : i64
%9 = arith.constant 2 : i32
%11 = arith.extsi %9 : i32 to i64
%10 = arith.divsi %7, %11 : i64
%12 = llvm.mlir.constant(1 : i64) : i64
%13 = llvm.alloca %12 x i64 : (i64) -> !llvm.ptr
llvm.store %10, %13 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%14 = llvm.load %13 : !llvm.ptr -> i64
%15 = llvm.load %4 : !llvm.ptr -> i64
%16 = arith.cmpi slt, %14, %15 : i64
cf.cond_br %16, ^bb4, ^bb5
^bb4:
%17 = llvm.load %13 : !llvm.ptr -> i64
llvm.store %17, %4 : i64, !llvm.ptr
%18 = llvm.load %4 : !llvm.ptr -> i64
%19 = llvm.load %4 : !llvm.ptr -> i64
%20 = arith.divsi %arg0, %19 : i64
%21 = arith.addi %18, %20 : i64
%22 = arith.constant 2 : i32
%24 = arith.extsi %22 : i32 to i64
%23 = arith.divsi %21, %24 : i64
llvm.store %23, %13 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%25 = llvm.load %4 : !llvm.ptr -> i64
func.return %25 : i64
}
func.func @easy_prefix(%arg0: i64) -> i64 {
%26 = arith.constant 3 : i32
%28 = arith.extsi %26 : i32 to i64
%27 = arith.cmpi slt, %arg0, %28 : i64
cf.cond_br %27, ^bb6, ^bb7
^bb6:
%29 = arith.constant 0 : i32
%30 = arith.extsi %29 : i32 to i64
func.return %30 : i64
^bb7:
cf.br ^bb8
^bb8:
%31 = llvm.mlir.addressof @MOD : !llvm.ptr
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 6 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.muli %32, %35 : i64
%36 = arith.extsi %arg0 : i64 to i128
%37 = arith.extsi %arg0 : i64 to i128
%39 = arith.trunci %36 : i128 to i64
%40 = arith.trunci %37 : i128 to i64
%38 = arith.muli %39, %40 : i64
%41 = arith.extsi %34 : i64 to i128
%43 = arith.trunci %41 : i128 to i64
%42 = arith.remsi %38, %43 : i64
%44 = arith.extsi %arg0 : i64 to i128
%46 = arith.trunci %44 : i128 to i64
%45 = arith.muli %42, %46 : i64
%47 = arith.extsi %34 : i64 to i128
%49 = arith.trunci %47 : i128 to i64
%48 = arith.remsi %45, %49 : i64
%50 = arith.extsi %arg0 : i64 to i128
%51 = arith.extsi %arg0 : i64 to i128
%53 = arith.trunci %50 : i128 to i64
%54 = arith.trunci %51 : i128 to i64
%52 = arith.muli %53, %54 : i64
%55 = arith.extsi %34 : i64 to i128
%57 = arith.trunci %55 : i128 to i64
%56 = arith.remsi %52, %57 : i64
%58 = arith.constant 15 : i32
%60 = arith.extsi %58 : i32 to i64
%59 = arith.muli %60, %56 : i64
%61 = arith.remsi %59, %34 : i64
%62 = arith.addi %48, %61 : i64
%63 = arith.constant 52 : i32
%65 = arith.extsi %63 : i32 to i64
%64 = arith.muli %65, %arg0 : i64
%66 = arith.remsi %64, %34 : i64
%67 = arith.subi %34, %66 : i64
%68 = arith.addi %62, %67 : i64
%69 = arith.constant 36 : i32
%71 = arith.extsi %69 : i32 to i64
%70 = arith.addi %68, %71 : i64
%72 = arith.remsi %70, %34 : i64
%73 = arith.constant 6 : i32
%75 = arith.extsi %73 : i32 to i64
%74 = arith.divsi %72, %75 : i64
func.return %74 : i64
}
func.func @min_n_and_square(%arg0: i64, %arg1: i64, %arg2: !llvm.ptr) -> i64 {
%76 = arith.constant 4 : i32
%77 = arith.constant 1 : i32
%79 = arith.extsi %77 : i32 to i64
%78 = arith.addi %arg0, %79 : i64
%80 = arith.muli %arg0, %78 : i64
%82 = arith.extsi %76 : i32 to i64
%81 = arith.muli %82, %80 : i64
%83 = arith.constant 1 : i32
%85 = arith.extsi %83 : i32 to i64
%84 = arith.addi %arg1, %85 : i64
%86 = arith.muli %arg1, %84 : i64
%87 = arith.muli %81, %86 : i64
%88 = func.call @isqrt_i64(%87) : (i64) -> i64
%89 = arith.muli %88, %88 : i64
%90 = arith.cmpi eq, %89, %87 : i64
cf.cond_br %90, ^bb9, ^bb10
^bb9:
%91 = arith.constant 1 : i32
%92 = arith.constant 0 : i32
%93 = arith.extsi %92 : i32 to i64
%94 = llvm.getelementptr %arg2[%93] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %91, %94 : i32, !llvm.ptr
%95 = arith.constant 2 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.muli %97, %arg0 : i64
%98 = arith.muli %96, %arg1 : i64
%99 = arith.addi %98, %arg0 : i64
%100 = arith.addi %99, %arg1 : i64
%101 = arith.constant 1 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.addi %100, %103 : i64
%104 = arith.addi %102, %88 : i64
func.return %104 : i64
^bb10:
cf.br ^bb11
^bb11:
%105 = arith.constant 0 : i32
%106 = arith.constant 0 : i32
%107 = arith.extsi %106 : i32 to i64
%108 = llvm.getelementptr %arg2[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %105, %108 : i32, !llvm.ptr
%109 = arith.constant 2 : i32
%111 = arith.extsi %109 : i32 to i64
%110 = arith.muli %111, %arg0 : i64
%112 = arith.muli %110, %arg1 : i64
%113 = arith.addi %112, %arg0 : i64
%114 = arith.addi %113, %arg1 : i64
%115 = arith.constant 1 : i32
%117 = arith.extsi %115 : i32 to i64
%116 = arith.addi %114, %117 : i64
%118 = arith.constant 1 : i32
%120 = arith.extsi %118 : i32 to i64
%119 = arith.addi %88, %120 : i64
%121 = arith.addi %116, %119 : i64
func.return %121 : i64
}
func.func @y_max_for_x(%arg0: i64, %arg1: i64) -> i64 {
%122 = arith.constant 4 : i32
%124 = arith.extsi %122 : i32 to i64
%123 = arith.muli %124, %arg1 : i64
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.subi %arg0, %127 : i64
%128 = arith.cmpi sgt, %123, %126 : i64
cf.cond_br %128, ^bb12, ^bb13
^bb12:
%129 = arith.constant 1 : i32
%131 = arith.extsi %129 : i32 to i64
%130 = arith.subi %arg1, %131 : i64
func.return %130 : i64
^bb13:
cf.br ^bb14
^bb14:
%132 = arith.constant 1 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.subi %arg0, %134 : i64
%135 = arith.constant 4 : i32
%137 = arith.extsi %135 : i32 to i64
%136 = arith.muli %137, %arg1 : i64
%138 = arith.divsi %133, %136 : i64
%139 = arith.constant 2 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.addi %138, %141 : i64
%142 = llvm.mlir.constant(1 : i64) : i64
%143 = llvm.alloca %142 x i64 : (i64) -> !llvm.ptr
llvm.store %140, %143 : i64, !llvm.ptr
%144 = llvm.load %143 : !llvm.ptr -> i64
%145 = arith.cmpi slt, %144, %arg1 : i64
cf.cond_br %145, ^bb15, ^bb16
^bb15:
llvm.store %arg1, %143 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%146 = llvm.mlir.constant(1 : i64) : i64
%147 = llvm.alloca %146 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %147 : i64, !llvm.ptr
%148 = arith.constant 1 : i32
%150 = arith.extsi %148 : i32 to i64
%149 = arith.subi %arg1, %150 : i64
%151 = llvm.mlir.constant(1 : i64) : i64
%152 = llvm.alloca %151 x i64 : (i64) -> !llvm.ptr
llvm.store %149, %152 : i64, !llvm.ptr
%154 = arith.constant 1 : i32
%155 = arith.constant 4 : i32
%156 = arith.extsi %154 : i32 to i64
%157 = arith.extsi %155 : i32 to i64
%153 = func.call @calloc(%156, %157) : (i64, i64) -> !llvm.ptr
cf.br ^bb18
^bb18:
%158 = llvm.load %147 : !llvm.ptr -> i64
%159 = llvm.load %143 : !llvm.ptr -> i64
%160 = arith.cmpi sle, %158, %159 : i64
cf.cond_br %160, ^bb19, ^bb20
^bb19:
%161 = llvm.load %147 : !llvm.ptr -> i64
%162 = llvm.load %143 : !llvm.ptr -> i64
%163 = arith.addi %161, %162 : i64
%164 = arith.constant 2 : i32
%166 = arith.extsi %164 : i32 to i64
%165 = arith.divsi %163, %166 : i64
%167 = func.call @min_n_and_square(%arg1, %165, %153) : (i64, i64, !llvm.ptr) -> i64
%168 = arith.cmpi sle, %167, %arg0 : i64
cf.cond_br %168, ^bb21, ^bb22
^bb21:
llvm.store %165, %152 : i64, !llvm.ptr
%169 = arith.constant 1 : i32
%171 = arith.extsi %169 : i32 to i64
%170 = arith.addi %165, %171 : i64
llvm.store %170, %147 : i64, !llvm.ptr
cf.br ^bb23
^bb22:
%172 = arith.constant 1 : i32
%174 = arith.extsi %172 : i32 to i64
%173 = arith.subi %165, %174 : i64
llvm.store %173, %143 : i64, !llvm.ptr
cf.br ^bb23
^bb23:
cf.br ^bb18
^bb20:
func.call @free(%153) : (!llvm.ptr) -> ()
%176 = llvm.load %152 : !llvm.ptr -> i64
func.return %176 : i64
}
func.func @hard_prefix(%arg0: i64) -> i64 {
%177 = arith.constant 3 : i32
%179 = arith.extsi %177 : i32 to i64
%178 = arith.cmpi slt, %arg0, %179 : i64
cf.cond_br %178, ^bb24, ^bb25
^bb24:
%180 = arith.constant 0 : i32
%181 = arith.extsi %180 : i32 to i64
func.return %181 : i64
^bb25:
cf.br ^bb26
^bb26:
%182 = arith.constant 1 : i32
%184 = arith.extsi %182 : i32 to i64
%183 = arith.subi %arg0, %184 : i64
%185 = arith.constant 4 : i32
%187 = arith.extsi %185 : i32 to i64
%186 = arith.divsi %183, %187 : i64
%188 = arith.constant 0 : i32
%190 = arith.extsi %188 : i32 to i64
%189 = arith.cmpi sle, %186, %190 : i64
cf.cond_br %189, ^bb27, ^bb28
^bb27:
%191 = arith.constant 0 : i32
%192 = arith.extsi %191 : i32 to i64
func.return %192 : i64
^bb28:
cf.br ^bb29
^bb29:
%193 = func.call @isqrt_i64(%186) : (i64) -> i64
%194 = arith.constant 0 : i32
%195 = arith.extsi %194 : i32 to i64
%196 = llvm.mlir.constant(1 : i64) : i64
%197 = llvm.alloca %196 x i64 : (i64) -> !llvm.ptr
llvm.store %195, %197 : i64, !llvm.ptr
%198 = llvm.mlir.addressof @MOD : !llvm.ptr
%199 = llvm.load %198 : !llvm.ptr -> i64
%200 = arith.constant 20 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.shli %199, %202 : i64
%203 = arith.constant 1 : i32
%204 = arith.constant 1 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.addi %193, %206 : i64
%207 = arith.index_cast %203 : i32 to index
%208 = arith.index_cast %205 : i32 to index
%210 = arith.constant 1 : index
%211 = arith.constant -1 : index
%212 = arith.cmpi sle, %207, %208 : index
%209 = arith.select %212, %210, %211 : index
cf.br ^bb30(%207 : index)
^bb30(%213: index):
%214 = arith.cmpi slt, %213, %208 : index
%215 = arith.cmpi sgt, %213, %208 : index
%216 = arith.select %212, %214, %215 : i1
cf.cond_br %216, ^bb31(%213 : index), ^bb32(%213 : index)
^bb31(%217: index):
%219 = arith.index_cast %217 : index to i64
%218 = func.call @y_max_for_x(%arg0, %219) : (i64, i64) -> i64
%221 = arith.trunci %218 : i64 to i32
%222 = arith.index_cast %217 : index to i32
%220 = arith.cmpi slt, %221, %222 : i32
cf.cond_br %220, ^bb33, ^bb34
^bb33:
%223 = arith.addi %217, %209 : index
cf.br ^bb30(%223 : index)
^bb34:
cf.br ^bb35
^bb35:
%224 = arith.constant 1 : i32
%226 = arith.index_cast %217 : index to i32
%225 = arith.addi %226, %224 : i32
%228 = arith.index_cast %217 : index to i32
%227 = arith.muli %228, %225 : i32
%229 = arith.extsi %227 : i32 to i64
%230 = arith.index_cast %217 : index to i64
%231 = llvm.mlir.constant(1 : i64) : i64
%232 = llvm.alloca %231 x i64 : (i64) -> !llvm.ptr
llvm.store %230, %232 : i64, !llvm.ptr
%233 = llvm.load %232 : !llvm.ptr -> i64
%234 = llvm.load %232 : !llvm.ptr -> i64
%235 = arith.constant 1 : i32
%237 = arith.extsi %235 : i32 to i64
%236 = arith.addi %234, %237 : i64
%238 = arith.muli %233, %236 : i64
%239 = llvm.mlir.constant(1 : i64) : i64
%240 = llvm.alloca %239 x i64 : (i64) -> !llvm.ptr
llvm.store %238, %240 : i64, !llvm.ptr
%241 = arith.constant 2 : i32
%243 = arith.index_cast %217 : index to i32
%242 = arith.muli %241, %243 : i32
%244 = llvm.load %232 : !llvm.ptr -> i64
%246 = arith.extsi %242 : i32 to i64
%245 = arith.muli %246, %244 : i64
%247 = llvm.mlir.constant(1 : i64) : i64
%248 = llvm.alloca %247 x i64 : (i64) -> !llvm.ptr
llvm.store %245, %248 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%249 = llvm.load %232 : !llvm.ptr -> i64
%250 = arith.cmpi sle, %249, %218 : i64
cf.cond_br %250, ^bb37, ^bb38
^bb37:
%251 = llvm.load %240 : !llvm.ptr -> i64
%252 = arith.muli %229, %251 : i64
%253 = arith.constant 2 : i32
%255 = arith.extsi %253 : i32 to i64
%254 = arith.shli %252, %255 : i64
%256 = func.call @isqrt_i64(%254) : (i64) -> i64
%257 = arith.constant 0 : i32
%258 = llvm.mlir.constant(1 : i64) : i64
%259 = llvm.alloca %258 x i32 : (i64) -> !llvm.ptr
llvm.store %257, %259 : i32, !llvm.ptr
%260 = arith.muli %256, %256 : i64
%261 = arith.cmpi eq, %260, %254 : i64
cf.cond_br %261, ^bb39, ^bb40
^bb39:
%262 = arith.constant 1 : i32
llvm.store %262, %259 : i32, !llvm.ptr
cf.br ^bb41
^bb40:
cf.br ^bb41
^bb41:
%263 = arith.constant 0 : i32
%264 = arith.extsi %263 : i32 to i64
%265 = llvm.mlir.constant(1 : i64) : i64
%266 = llvm.alloca %265 x i64 : (i64) -> !llvm.ptr
llvm.store %264, %266 : i64, !llvm.ptr
%267 = llvm.load %259 : !llvm.ptr -> i32
%268 = arith.constant 0 : i32
%269 = arith.cmpi ne, %267, %268 : i32
cf.cond_br %269, ^bb42, ^bb43
^bb42:
llvm.store %256, %266 : i64, !llvm.ptr
cf.br ^bb44
^bb43:
%270 = arith.constant 1 : i32
%272 = arith.extsi %270 : i32 to i64
%271 = arith.addi %256, %272 : i64
llvm.store %271, %266 : i64, !llvm.ptr
cf.br ^bb44
^bb44:
%273 = llvm.load %248 : !llvm.ptr -> i64
%275 = arith.trunci %273 : i64 to i32
%276 = arith.index_cast %217 : index to i32
%274 = arith.addi %275, %276 : i32
%277 = llvm.load %232 : !llvm.ptr -> i64
%279 = arith.extsi %274 : i32 to i64
%278 = arith.addi %279, %277 : i64
%280 = arith.constant 1 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.addi %278, %282 : i64
%283 = llvm.load %266 : !llvm.ptr -> i64
%284 = arith.addi %281, %283 : i64
%285 = arith.cmpi sle, %284, %arg0 : i64
cf.cond_br %285, ^bb45, ^bb46
^bb45:
%286 = arith.constant 2 : i32
%287 = arith.subi %arg0, %284 : i64
%288 = arith.constant 1 : i32
%290 = arith.extsi %288 : i32 to i64
%289 = arith.addi %287, %290 : i64
%292 = arith.extsi %286 : i32 to i64
%291 = arith.muli %292, %289 : i64
%293 = llvm.load %259 : !llvm.ptr -> i32
%294 = arith.extsi %293 : i32 to i64
%295 = arith.subi %291, %294 : i64
%296 = llvm.mlir.constant(1 : i64) : i64
%297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
llvm.store %295, %297 : i64, !llvm.ptr
%298 = llvm.load %232 : !llvm.ptr -> i64
%300 = arith.index_cast %217 : index to i32
%301 = arith.trunci %298 : i64 to i32
%299 = arith.cmpi ne, %300, %301 : i32
cf.cond_br %299, ^bb48, ^bb49
^bb48:
%302 = arith.constant 1 : i32
%304 = arith.extsi %302 : i32 to i64
%303 = arith.shli %295, %304 : i64
llvm.store %303, %297 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%305 = llvm.load %197 : !llvm.ptr -> i64
%306 = llvm.load %297 : !llvm.ptr -> i64
%307 = arith.addi %305, %306 : i64
llvm.store %307, %197 : i64, !llvm.ptr
%308 = llvm.load %197 : !llvm.ptr -> i64
%309 = arith.cmpi sge, %308, %201 : i64
cf.cond_br %309, ^bb51, ^bb52
^bb51:
%310 = llvm.load %197 : !llvm.ptr -> i64
%311 = llvm.mlir.addressof @MOD : !llvm.ptr
%312 = llvm.load %311 : !llvm.ptr -> i64
%313 = arith.remsi %310, %312 : i64
llvm.store %313, %197 : i64, !llvm.ptr
cf.br ^bb53
^bb52:
cf.br ^bb53
^bb53:
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%314 = llvm.load %240 : !llvm.ptr -> i64
%315 = llvm.load %232 : !llvm.ptr -> i64
%316 = arith.constant 1 : i32
%318 = arith.extsi %316 : i32 to i64
%317 = arith.shli %315, %318 : i64
%319 = arith.constant 2 : i32
%321 = arith.extsi %319 : i32 to i64
%320 = arith.addi %317, %321 : i64
%322 = arith.addi %314, %320 : i64
llvm.store %322, %240 : i64, !llvm.ptr
%323 = llvm.load %232 : !llvm.ptr -> i64
%324 = arith.constant 1 : i32
%326 = arith.extsi %324 : i32 to i64
%325 = arith.addi %323, %326 : i64
llvm.store %325, %232 : i64, !llvm.ptr
%327 = llvm.load %248 : !llvm.ptr -> i64
%328 = arith.constant 1 : i32
%330 = arith.index_cast %217 : index to i32
%329 = arith.shli %330, %328 : i32
%332 = arith.extsi %329 : i32 to i64
%331 = arith.addi %327, %332 : i64
llvm.store %331, %248 : i64, !llvm.ptr
cf.br ^bb36
^bb38:
%333 = arith.addi %217, %209 : index
cf.br ^bb30(%333 : index)
^bb32(%334: index):
%335 = llvm.load %197 : !llvm.ptr -> i64
%336 = llvm.mlir.addressof @MOD : !llvm.ptr
%337 = llvm.load %336 : !llvm.ptr -> i64
%338 = arith.remsi %335, %337 : i64
func.return %338 : i64
}
func.func @main() -> i32 {
%339 = arith.constant 100000000 : i32
%340 = arith.extsi %339 : i32 to i64
%341 = func.call @easy_prefix(%340) : (i64) -> i64
%342 = func.call @hard_prefix(%340) : (i64) -> i64
%343 = arith.constant 3 : i32
%345 = arith.extsi %343 : i32 to i64
%344 = arith.muli %345, %342 : i64
%346 = arith.addi %341, %344 : i64
%347 = llvm.mlir.addressof @MOD : !llvm.ptr
%348 = llvm.load %347 : !llvm.ptr -> i64
%349 = arith.remsi %346, %348 : i64
%350 = llvm.mlir.addressof @str_0 : !llvm.ptr
%351 = llvm.call @printf(%350, %349) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%352 = arith.constant 0 : i32
func.return %352 : i32
}
}