← All problems Problem 771
Pseudo-geometric sequences: strictly increasing a_0 < ... < a_n of positive integers, n >= 4, with |a_i^2 - a_{i-1}a_{i+1}| <= 2 at every interior i. G(N) counts them with all terms <= N; find G(10^18) mod 1e9+7. Brute-force enumeration up to N = 316227 (pair-graph DFS) shows every such sequence falls into exactly one class: runs k,k+1,...,k+m (m >= 4): (N-4)(N-3)/2 geometric, ratio p/q > 1, L terms: sum over L>=5, p of phi(p) * floor(N / p^(L-1)) (start t*q^(L-1), t = 1,2,...) windows of >= 5 consecutive terms of the Lucas-type sequences Fibonacci 1,2,3,5,8,... (x' = 1*x + prev) NSW 1,3,7,17,... (x' = 2*x + prev) 1,2,5,13,34,... 1,3,11,41,... (x' = 3*x - prev, 4*x - prev) A_P: 1,P,P^2-1,... (P >= 3) (x' = P*x - prev) B_P: 1,P,P^2+1,... (P >= 2) (x' = P*x + prev) a sequence of m terms <= N gives (m-4)(m-3)/2 windows the hybrid prefix family 1,2,6,18,...,2*3^k (k >= 3) 10 sporadic sequences whose largest terms are 6,9,9,9,12,16,16,20,48,60 The class list reproduces the full brute-force sequence sets at N = 10^3, 2*10^3, 5*10^3, 10^4, 10^5, 316227 and G(N) at 28 values.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n log log n)Space complexity O(n)O(n)Approach Flow solution Sieve-based totient computation Verdict Suboptimal
Flow source
# Project Euler 771
# Pseudo-geometric sequences: strictly increasing a_0 < ... < a_n of positive
# integers, n >= 4, with |a_i^2 - a_{i-1}a_{i+1}| <= 2 at every interior i.
# G(N) counts them with all terms <= N; find G(10^18) mod 1e9+7.
#
# Brute-force enumeration up to N = 316227 (pair-graph DFS) shows every such
# sequence falls into exactly one class:
# runs k,k+1,...,k+m (m >= 4): (N-4)(N-3)/2
# geometric, ratio p/q > 1, L terms: sum over L>=5, p of
# phi(p) * floor(N / p^(L-1)) (start t*q^(L-1), t = 1,2,...)
# windows of >= 5 consecutive terms of the Lucas-type sequences
# Fibonacci 1,2,3,5,8,... (x' = 1*x + prev)
# NSW 1,3,7,17,... (x' = 2*x + prev)
# 1,2,5,13,34,... 1,3,11,41,... (x' = 3*x - prev, 4*x - prev)
# A_P: 1,P,P^2-1,... (P >= 3) (x' = P*x - prev)
# B_P: 1,P,P^2+1,... (P >= 2) (x' = P*x + prev)
# a sequence of m terms <= N gives (m-4)(m-3)/2 windows
# the hybrid prefix family 1,2,6,18,...,2*3^k (k >= 3)
# 10 sporadic sequences whose largest terms are
# 6,9,9,9,12,16,16,20,48,60
# The class list reproduces the full brute-force sequence sets at
# N = 10^3, 2*10^3, 5*10^3, 10^4, 10^5, 316227 and G(N) at 28 values.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const N: i64 = 1000000000000000000
const MOD: i64 = 1000000007
# number of >= 5 term windows with max term <= N of the infinite sequence
# x0, x1, then x_{k+1} = P*x_k - Q*x_{k-1}
function windows(x0: i64, x1: i64, P: i64, Q: i64) -> i64 {
if x1 > N {
return 0
}
let mut t0: i64 = x0
let mut t1: i64 = x1
let mut m: i64 = 2
let mut go: i64 = 1
while go == 1 {
let nxt: i128 = (P as i128) * (t1 as i128) - (Q as i128) * (t0 as i128)
if nxt > (N as i128) {
go = 0
} else {
t0 = t1
t1 = nxt as i64
m = m + 1
}
}
if m >= 5 {
return (m - 4) * (m - 3) / 2
}
return 0
}
function main() -> i32 {
# ---- runs: (N-4)(N-3)/2 mod MOD ----
let mut ra: i64 = N - 4
let mut rb: i64 = N - 3
if ra % 2 == 0 {
ra = ra / 2
} else {
rb = rb / 2
}
let mut total: i64 = ((((ra % MOD) as i128) * ((rb % MOD) as i128)) % (MOD as i128)) as i64
# ---- geometric: phi sieve up to floor(N^(1/4)) ----
let mut p4: i64 = 1
let mut grow: i64 = 1
while grow == 1 {
let s: i64 = p4 + 1
let s2: i64 = s * s
if s2 * s2 <= N {
p4 = s
} else {
grow = 0
}
}
let phi: ptr<i64> = calloc(p4 + 1, 8)
let mut i: i64 = 0
while i <= p4 {
phi[i] = i
i = i + 1
}
i = 2
while i <= p4 {
if phi[i] == i {
let mut j: i64 = i
while j <= p4 {
phi[j] = phi[j] - phi[j] / i
j = j + i
}
}
i = i + 1
}
let mut p: i64 = 2
while p <= p4 {
let mut pw: i64 = p * p * p * p
while pw <= N {
total = (total + phi[p] * ((N / pw) % MOD)) % MOD
if pw <= N / p {
pw = pw * p
} else {
pw = N + 1
}
}
p = p + 1
}
free(phi)
# ---- Lucas-type windows ----
total = (total + windows(1, 2, 1, 0 - 1)) % MOD # Fibonacci
total = (total + windows(1, 3, 2, 0 - 1)) % MOD # NSW
total = (total + windows(1, 2, 3, 1)) % MOD # 1,2,5,13,...
total = (total + windows(1, 3, 4, 1)) % MOD # 1,3,11,41,...
p = 2
while p <= p4 + 2 {
if p >= 3 {
total = (total + windows(1, p, p, 1)) % MOD
}
total = (total + windows(1, p, p, 0 - 1)) % MOD
p = p + 1
}
# ---- hybrid 1,2,6,18,...,2*3^k (k >= 3) ----
let mut v: i64 = 54
while v <= N {
total = (total + 1) % MOD
v = v * 3
}
# ---- sporadics ----
let mx: ptr<i64> = calloc(10, 8)
mx[0] = 6
mx[1] = 9
mx[2] = 9
mx[3] = 9
mx[4] = 12
mx[5] = 16
mx[6] = 16
mx[7] = 20
mx[8] = 48
mx[9] = 60
i = 0
while i < 10 {
if mx[i] <= N {
total = (total + 1) % MOD
}
i = i + 1
}
free(mx)
printf("%lld\n", total)
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 windows_i64_i64_i64_i64(int64_t x0, int64_t x1, int64_t P, int64_t Q);
int32_t main(void);
static const int64_t N = 1000000000000000000;
static const int64_t MOD = 1000000007;
int64_t windows_i64_i64_i64_i64(int64_t x0, int64_t x1, int64_t P, int64_t Q) {
if (x1 > N) {
return 0;
}
int64_t t0 = x0;
int64_t t1 = x1;
int64_t m = 2;
int64_t go = 1;
while (go == 1) {
__int128 nxt = ((((__int128)(P)) * ((__int128)(t1))) - (((__int128)(Q)) * ((__int128)(t0))));
if (nxt > ((__int128)(N))) {
go = 0;
} else {
t0 = t1;
t1 = ((int64_t)(nxt));
m = (m + 1);
}
}
if (m >= 5) {
return FLOW_CHECKED_DIV((((m - 4) * (m - 3))), (2));
}
return 0;
}
int32_t main(void) {
int64_t ra = (N - 4);
int64_t rb = (N - 3);
if (FLOW_CHECKED_MOD((ra), (2)) == 0) {
ra = FLOW_CHECKED_DIV((ra), (2));
} else {
rb = FLOW_CHECKED_DIV((rb), (2));
}
int64_t total = ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(FLOW_CHECKED_MOD((ra), (MOD)))) * ((__int128)(FLOW_CHECKED_MOD((rb), (MOD)))))), (((__int128)(MOD))))));
int64_t p4 = 1;
int64_t grow = 1;
while (grow == 1) {
int64_t s = (p4 + 1);
int64_t s2 = (s * s);
if ((s2 * s2) <= N) {
p4 = s;
} else {
grow = 0;
}
}
int64_t* phi = (int64_t*)(calloc((p4 + 1), 8));
int64_t i = 0;
while (i <= p4) {
phi[i] = i;
i = (i + 1);
}
i = 2;
while (i <= p4) {
if (phi[i] == i) {
int64_t j = i;
while (j <= p4) {
phi[j] = (phi[j] - FLOW_CHECKED_DIV((phi[j]), (i)));
j = (j + i);
}
}
i = (i + 1);
}
int64_t p = 2;
while (p <= p4) {
int64_t pw = (((p * p) * p) * p);
while (pw <= N) {
total = FLOW_CHECKED_MOD(((total + (phi[p] * FLOW_CHECKED_MOD((FLOW_CHECKED_DIV((N), (pw))), (MOD))))), (MOD));
if (pw <= FLOW_CHECKED_DIV((N), (p))) {
pw = (pw * p);
} else {
pw = (N + 1);
}
}
p = (p + 1);
}
free(phi);
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, 2, 1, (0 - 1)))), (MOD));
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, 3, 2, (0 - 1)))), (MOD));
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, 2, 3, 1))), (MOD));
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, 3, 4, 1))), (MOD));
p = 2;
while (p <= (p4 + 2)) {
if (p >= 3) {
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, p, p, 1))), (MOD));
}
total = FLOW_CHECKED_MOD(((total + windows_i64_i64_i64_i64(1, p, p, (0 - 1)))), (MOD));
p = (p + 1);
}
int64_t v = 54;
while (v <= N) {
total = FLOW_CHECKED_MOD(((total + 1)), (MOD));
v = (v * 3);
}
int64_t* mx = (int64_t*)(calloc(10, 8));
mx[0] = 6;
mx[1] = 9;
mx[2] = 9;
mx[3] = 9;
mx[4] = 12;
mx[5] = 16;
mx[6] = 16;
mx[7] = 20;
mx[8] = 48;
mx[9] = 60;
i = 0;
while (i < 10) {
if (mx[i] <= N) {
total = FLOW_CHECKED_MOD(((total + 1)), (MOD));
}
i = (i + 1);
}
free(mx);
printf("%lld\n", total);
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: N
llvm.mlir.global internal constant @N(1000000000000000000 : i64) : i64
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
func.func @windows(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64) -> i64 {
%0 = llvm.mlir.addressof @N : !llvm.ptr
%1 = llvm.load %0 : !llvm.ptr -> i64
%2 = arith.cmpi sgt, %arg1, %1 : i64
cf.cond_br %2, ^bb0, ^bb1
^bb0:
%3 = arith.constant 0 : i32
%4 = arith.extsi %3 : i32 to i64
func.return %4 : i64
^bb1:
cf.br ^bb2
^bb2:
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i64 : (i64) -> !llvm.ptr
llvm.store %arg0, %6 : i64, !llvm.ptr
%7 = llvm.mlir.constant(1 : i64) : i64
%8 = llvm.alloca %7 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %8 : i64, !llvm.ptr
%9 = arith.constant 2 : i32
%10 = arith.extsi %9 : i32 to i64
%11 = llvm.mlir.constant(1 : i64) : i64
%12 = llvm.alloca %11 x i64 : (i64) -> !llvm.ptr
llvm.store %10, %12 : i64, !llvm.ptr
%13 = arith.constant 1 : 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 %16 : !llvm.ptr -> i64
%18 = arith.constant 1 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.cmpi eq, %17, %20 : i64
cf.cond_br %19, ^bb4, ^bb5
^bb4:
%21 = arith.extsi %arg2 : i64 to i128
%22 = llvm.load %8 : !llvm.ptr -> i64
%23 = arith.extsi %22 : i64 to i128
%25 = arith.trunci %21 : i128 to i64
%26 = arith.trunci %23 : i128 to i64
%24 = arith.muli %25, %26 : i64
%27 = arith.extsi %arg3 : i64 to i128
%28 = llvm.load %6 : !llvm.ptr -> i64
%29 = arith.extsi %28 : i64 to i128
%31 = arith.trunci %27 : i128 to i64
%32 = arith.trunci %29 : i128 to i64
%30 = arith.muli %31, %32 : i64
%33 = arith.subi %24, %30 : i64
%34 = arith.extsi %33 : i64 to i128
%35 = llvm.mlir.addressof @N : !llvm.ptr
%36 = llvm.load %35 : !llvm.ptr -> i64
%37 = arith.extsi %36 : i64 to i128
%39 = arith.trunci %34 : i128 to i64
%40 = arith.trunci %37 : i128 to i64
%38 = arith.cmpi sgt, %39, %40 : i64
cf.cond_br %38, ^bb6, ^bb7
^bb6:
%41 = arith.constant 0 : i32
%42 = arith.extsi %41 : i32 to i64
llvm.store %42, %16 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
%43 = llvm.load %8 : !llvm.ptr -> i64
llvm.store %43, %6 : i64, !llvm.ptr
%44 = arith.trunci %34 : i128 to i64
llvm.store %44, %8 : i64, !llvm.ptr
%45 = llvm.load %12 : !llvm.ptr -> i64
%46 = arith.constant 1 : i32
%48 = arith.extsi %46 : i32 to i64
%47 = arith.addi %45, %48 : i64
llvm.store %47, %12 : i64, !llvm.ptr
cf.br ^bb8
^bb8:
cf.br ^bb3
^bb5:
%49 = llvm.load %12 : !llvm.ptr -> i64
%50 = arith.constant 5 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.cmpi sge, %49, %52 : i64
cf.cond_br %51, ^bb9, ^bb10
^bb9:
%53 = llvm.load %12 : !llvm.ptr -> i64
%54 = arith.constant 4 : i32
%56 = arith.extsi %54 : i32 to i64
%55 = arith.subi %53, %56 : i64
%57 = llvm.load %12 : !llvm.ptr -> i64
%58 = arith.constant 3 : i32
%60 = arith.extsi %58 : i32 to i64
%59 = arith.subi %57, %60 : i64
%61 = arith.muli %55, %59 : i64
%62 = arith.constant 2 : i32
%64 = arith.extsi %62 : i32 to i64
%63 = arith.divsi %61, %64 : i64
func.return %63 : i64
^bb10:
cf.br ^bb11
^bb11:
%65 = arith.constant 0 : i32
%66 = arith.extsi %65 : i32 to i64
func.return %66 : i64
}
func.func @main() -> i32 {
%67 = llvm.mlir.addressof @N : !llvm.ptr
%68 = llvm.load %67 : !llvm.ptr -> i64
%69 = arith.constant 4 : i32
%71 = arith.extsi %69 : i32 to i64
%70 = arith.subi %68, %71 : i64
%72 = llvm.mlir.constant(1 : i64) : i64
%73 = llvm.alloca %72 x i64 : (i64) -> !llvm.ptr
llvm.store %70, %73 : i64, !llvm.ptr
%74 = llvm.mlir.addressof @N : !llvm.ptr
%75 = llvm.load %74 : !llvm.ptr -> i64
%76 = arith.constant 3 : i32
%78 = arith.extsi %76 : i32 to i64
%77 = arith.subi %75, %78 : i64
%79 = llvm.mlir.constant(1 : i64) : i64
%80 = llvm.alloca %79 x i64 : (i64) -> !llvm.ptr
llvm.store %77, %80 : i64, !llvm.ptr
%81 = llvm.load %73 : !llvm.ptr -> i64
%82 = arith.constant 2 : i32
%84 = arith.extsi %82 : i32 to i64
%83 = arith.remsi %81, %84 : i64
%85 = arith.constant 0 : i32
%87 = arith.extsi %85 : i32 to i64
%86 = arith.cmpi eq, %83, %87 : i64
cf.cond_br %86, ^bb12, ^bb13
^bb12:
%88 = llvm.load %73 : !llvm.ptr -> i64
%89 = arith.constant 2 : i32
%91 = arith.extsi %89 : i32 to i64
%90 = arith.divsi %88, %91 : i64
llvm.store %90, %73 : i64, !llvm.ptr
cf.br ^bb14
^bb13:
%92 = llvm.load %80 : !llvm.ptr -> i64
%93 = arith.constant 2 : i32
%95 = arith.extsi %93 : i32 to i64
%94 = arith.divsi %92, %95 : i64
llvm.store %94, %80 : i64, !llvm.ptr
cf.br ^bb14
^bb14:
%96 = llvm.load %73 : !llvm.ptr -> i64
%97 = llvm.mlir.addressof @MOD : !llvm.ptr
%98 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.remsi %96, %98 : i64
%100 = arith.extsi %99 : i64 to i128
%101 = llvm.load %80 : !llvm.ptr -> i64
%102 = llvm.mlir.addressof @MOD : !llvm.ptr
%103 = llvm.load %102 : !llvm.ptr -> i64
%104 = arith.remsi %101, %103 : i64
%105 = arith.extsi %104 : i64 to i128
%107 = arith.trunci %100 : i128 to i64
%108 = arith.trunci %105 : i128 to i64
%106 = arith.muli %107, %108 : i64
%109 = llvm.mlir.addressof @MOD : !llvm.ptr
%110 = llvm.load %109 : !llvm.ptr -> i64
%111 = arith.extsi %110 : i64 to i128
%113 = arith.trunci %111 : i128 to i64
%112 = arith.remsi %106, %113 : i64
%114 = llvm.mlir.constant(1 : i64) : i64
%115 = llvm.alloca %114 x i64 : (i64) -> !llvm.ptr
llvm.store %112, %115 : i64, !llvm.ptr
%116 = arith.constant 1 : i32
%117 = arith.extsi %116 : i32 to i64
%118 = llvm.mlir.constant(1 : i64) : i64
%119 = llvm.alloca %118 x i64 : (i64) -> !llvm.ptr
llvm.store %117, %119 : i64, !llvm.ptr
%120 = arith.constant 1 : i32
%121 = arith.extsi %120 : i32 to i64
%122 = llvm.mlir.constant(1 : i64) : i64
%123 = llvm.alloca %122 x i64 : (i64) -> !llvm.ptr
llvm.store %121, %123 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%124 = llvm.load %123 : !llvm.ptr -> i64
%125 = arith.constant 1 : i32
%127 = arith.extsi %125 : i32 to i64
%126 = arith.cmpi eq, %124, %127 : i64
cf.cond_br %126, ^bb16, ^bb17
^bb16:
%128 = llvm.load %119 : !llvm.ptr -> i64
%129 = arith.constant 1 : i32
%131 = arith.extsi %129 : i32 to i64
%130 = arith.addi %128, %131 : i64
%132 = arith.muli %130, %130 : i64
%133 = arith.muli %132, %132 : i64
%134 = llvm.mlir.addressof @N : !llvm.ptr
%135 = llvm.load %134 : !llvm.ptr -> i64
%136 = arith.cmpi sle, %133, %135 : i64
cf.cond_br %136, ^bb18, ^bb19
^bb18:
llvm.store %130, %119 : i64, !llvm.ptr
cf.br ^bb20
^bb19:
%137 = arith.constant 0 : i32
%138 = arith.extsi %137 : i32 to i64
llvm.store %138, %123 : i64, !llvm.ptr
cf.br ^bb20
^bb20:
cf.br ^bb15
^bb17:
%140 = llvm.load %119 : !llvm.ptr -> i64
%141 = arith.constant 1 : i32
%143 = arith.extsi %141 : i32 to i64
%142 = arith.addi %140, %143 : i64
%144 = arith.constant 8 : i32
%145 = arith.extsi %144 : i32 to i64
%139 = func.call @calloc(%142, %145) : (i64, i64) -> !llvm.ptr
%146 = arith.constant 0 : i32
%147 = arith.extsi %146 : i32 to i64
%148 = llvm.mlir.constant(1 : i64) : i64
%149 = llvm.alloca %148 x i64 : (i64) -> !llvm.ptr
llvm.store %147, %149 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%150 = llvm.load %149 : !llvm.ptr -> i64
%151 = llvm.load %119 : !llvm.ptr -> i64
%152 = arith.cmpi sle, %150, %151 : i64
cf.cond_br %152, ^bb22, ^bb23
^bb22:
%153 = llvm.load %149 : !llvm.ptr -> i64
%154 = llvm.load %149 : !llvm.ptr -> i64
%155 = llvm.getelementptr %139[%154] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %153, %155 : i64, !llvm.ptr
%156 = llvm.load %149 : !llvm.ptr -> i64
%157 = arith.constant 1 : i32
%159 = arith.extsi %157 : i32 to i64
%158 = arith.addi %156, %159 : i64
llvm.store %158, %149 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%160 = arith.constant 2 : i32
%161 = arith.extsi %160 : i32 to i64
llvm.store %161, %149 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%162 = llvm.load %149 : !llvm.ptr -> i64
%163 = llvm.load %119 : !llvm.ptr -> i64
%164 = arith.cmpi sle, %162, %163 : i64
cf.cond_br %164, ^bb25, ^bb26
^bb25:
%166 = llvm.load %149 : !llvm.ptr -> i64
%167 = llvm.getelementptr %139[%166] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%165 = llvm.load %167 : !llvm.ptr -> i64
%168 = llvm.load %149 : !llvm.ptr -> i64
%169 = arith.cmpi eq, %165, %168 : i64
cf.cond_br %169, ^bb27, ^bb28
^bb27:
%170 = llvm.load %149 : !llvm.ptr -> i64
%171 = llvm.mlir.constant(1 : i64) : i64
%172 = llvm.alloca %171 x i64 : (i64) -> !llvm.ptr
llvm.store %170, %172 : i64, !llvm.ptr
cf.br ^bb30
^bb30:
%173 = llvm.load %172 : !llvm.ptr -> i64
%174 = llvm.load %119 : !llvm.ptr -> i64
%175 = arith.cmpi sle, %173, %174 : i64
cf.cond_br %175, ^bb31, ^bb32
^bb31:
%177 = llvm.load %172 : !llvm.ptr -> i64
%178 = llvm.getelementptr %139[%177] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%176 = llvm.load %178 : !llvm.ptr -> i64
%180 = llvm.load %172 : !llvm.ptr -> i64
%181 = llvm.getelementptr %139[%180] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%179 = llvm.load %181 : !llvm.ptr -> i64
%182 = llvm.load %149 : !llvm.ptr -> i64
%183 = arith.divsi %179, %182 : i64
%184 = arith.subi %176, %183 : i64
%185 = llvm.load %172 : !llvm.ptr -> i64
%186 = llvm.getelementptr %139[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %184, %186 : i64, !llvm.ptr
%187 = llvm.load %172 : !llvm.ptr -> i64
%188 = llvm.load %149 : !llvm.ptr -> i64
%189 = arith.addi %187, %188 : i64
llvm.store %189, %172 : i64, !llvm.ptr
cf.br ^bb30
^bb32:
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%190 = llvm.load %149 : !llvm.ptr -> i64
%191 = arith.constant 1 : i32
%193 = arith.extsi %191 : i32 to i64
%192 = arith.addi %190, %193 : i64
llvm.store %192, %149 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%194 = arith.constant 2 : 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
cf.br ^bb33
^bb33:
%198 = llvm.load %197 : !llvm.ptr -> i64
%199 = llvm.load %119 : !llvm.ptr -> i64
%200 = arith.cmpi sle, %198, %199 : i64
cf.cond_br %200, ^bb34, ^bb35
^bb34:
%201 = llvm.load %197 : !llvm.ptr -> i64
%202 = llvm.load %197 : !llvm.ptr -> i64
%203 = arith.muli %201, %202 : i64
%204 = llvm.load %197 : !llvm.ptr -> i64
%205 = arith.muli %203, %204 : i64
%206 = llvm.load %197 : !llvm.ptr -> i64
%207 = arith.muli %205, %206 : i64
%208 = llvm.mlir.constant(1 : i64) : i64
%209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
llvm.store %207, %209 : i64, !llvm.ptr
cf.br ^bb36
^bb36:
%210 = llvm.load %209 : !llvm.ptr -> i64
%211 = llvm.mlir.addressof @N : !llvm.ptr
%212 = llvm.load %211 : !llvm.ptr -> i64
%213 = arith.cmpi sle, %210, %212 : i64
cf.cond_br %213, ^bb37, ^bb38
^bb37:
%214 = llvm.load %115 : !llvm.ptr -> i64
%216 = llvm.load %197 : !llvm.ptr -> i64
%217 = llvm.getelementptr %139[%216] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%215 = llvm.load %217 : !llvm.ptr -> i64
%218 = llvm.mlir.addressof @N : !llvm.ptr
%219 = llvm.load %218 : !llvm.ptr -> i64
%220 = llvm.load %209 : !llvm.ptr -> i64
%221 = arith.divsi %219, %220 : i64
%222 = llvm.mlir.addressof @MOD : !llvm.ptr
%223 = llvm.load %222 : !llvm.ptr -> i64
%224 = arith.remsi %221, %223 : i64
%225 = arith.muli %215, %224 : i64
%226 = arith.addi %214, %225 : i64
%227 = llvm.mlir.addressof @MOD : !llvm.ptr
%228 = llvm.load %227 : !llvm.ptr -> i64
%229 = arith.remsi %226, %228 : i64
llvm.store %229, %115 : i64, !llvm.ptr
%230 = llvm.load %209 : !llvm.ptr -> i64
%231 = llvm.mlir.addressof @N : !llvm.ptr
%232 = llvm.load %231 : !llvm.ptr -> i64
%233 = llvm.load %197 : !llvm.ptr -> i64
%234 = arith.divsi %232, %233 : i64
%235 = arith.cmpi sle, %230, %234 : i64
cf.cond_br %235, ^bb39, ^bb40
^bb39:
%236 = llvm.load %209 : !llvm.ptr -> i64
%237 = llvm.load %197 : !llvm.ptr -> i64
%238 = arith.muli %236, %237 : i64
llvm.store %238, %209 : i64, !llvm.ptr
cf.br ^bb41
^bb40:
%239 = llvm.mlir.addressof @N : !llvm.ptr
%240 = llvm.load %239 : !llvm.ptr -> i64
%241 = arith.constant 1 : i32
%243 = arith.extsi %241 : i32 to i64
%242 = arith.addi %240, %243 : i64
llvm.store %242, %209 : i64, !llvm.ptr
cf.br ^bb41
^bb41:
cf.br ^bb36
^bb38:
%244 = llvm.load %197 : !llvm.ptr -> i64
%245 = arith.constant 1 : i32
%247 = arith.extsi %245 : i32 to i64
%246 = arith.addi %244, %247 : i64
llvm.store %246, %197 : i64, !llvm.ptr
cf.br ^bb33
^bb35:
func.call @free(%139) : (!llvm.ptr) -> ()
%249 = llvm.load %115 : !llvm.ptr -> i64
%251 = arith.constant 1 : i32
%252 = arith.constant 2 : i32
%253 = arith.constant 1 : i32
%254 = arith.constant 0 : i32
%255 = arith.constant 1 : i32
%256 = arith.subi %254, %255 : i32
%257 = arith.extsi %251 : i32 to i64
%258 = arith.extsi %252 : i32 to i64
%259 = arith.extsi %253 : i32 to i64
%260 = arith.extsi %256 : i32 to i64
%250 = func.call @windows(%257, %258, %259, %260) : (i64, i64, i64, i64) -> i64
%261 = arith.addi %249, %250 : i64
%262 = llvm.mlir.addressof @MOD : !llvm.ptr
%263 = llvm.load %262 : !llvm.ptr -> i64
%264 = arith.remsi %261, %263 : i64
llvm.store %264, %115 : i64, !llvm.ptr
%265 = llvm.load %115 : !llvm.ptr -> i64
%267 = arith.constant 1 : i32
%268 = arith.constant 3 : i32
%269 = arith.constant 2 : i32
%270 = arith.constant 0 : i32
%271 = arith.constant 1 : i32
%272 = arith.subi %270, %271 : i32
%273 = arith.extsi %267 : i32 to i64
%274 = arith.extsi %268 : i32 to i64
%275 = arith.extsi %269 : i32 to i64
%276 = arith.extsi %272 : i32 to i64
%266 = func.call @windows(%273, %274, %275, %276) : (i64, i64, i64, i64) -> i64
%277 = arith.addi %265, %266 : i64
%278 = llvm.mlir.addressof @MOD : !llvm.ptr
%279 = llvm.load %278 : !llvm.ptr -> i64
%280 = arith.remsi %277, %279 : i64
llvm.store %280, %115 : i64, !llvm.ptr
%281 = llvm.load %115 : !llvm.ptr -> i64
%283 = arith.constant 1 : i32
%284 = arith.constant 2 : i32
%285 = arith.constant 3 : i32
%286 = arith.constant 1 : i32
%287 = arith.extsi %283 : i32 to i64
%288 = arith.extsi %284 : i32 to i64
%289 = arith.extsi %285 : i32 to i64
%290 = arith.extsi %286 : i32 to i64
%282 = func.call @windows(%287, %288, %289, %290) : (i64, i64, i64, i64) -> i64
%291 = arith.addi %281, %282 : i64
%292 = llvm.mlir.addressof @MOD : !llvm.ptr
%293 = llvm.load %292 : !llvm.ptr -> i64
%294 = arith.remsi %291, %293 : i64
llvm.store %294, %115 : i64, !llvm.ptr
%295 = llvm.load %115 : !llvm.ptr -> i64
%297 = arith.constant 1 : i32
%298 = arith.constant 3 : i32
%299 = arith.constant 4 : i32
%300 = arith.constant 1 : i32
%301 = arith.extsi %297 : i32 to i64
%302 = arith.extsi %298 : i32 to i64
%303 = arith.extsi %299 : i32 to i64
%304 = arith.extsi %300 : i32 to i64
%296 = func.call @windows(%301, %302, %303, %304) : (i64, i64, i64, i64) -> i64
%305 = arith.addi %295, %296 : i64
%306 = llvm.mlir.addressof @MOD : !llvm.ptr
%307 = llvm.load %306 : !llvm.ptr -> i64
%308 = arith.remsi %305, %307 : i64
llvm.store %308, %115 : i64, !llvm.ptr
%309 = arith.constant 2 : i32
%310 = arith.extsi %309 : i32 to i64
llvm.store %310, %197 : i64, !llvm.ptr
cf.br ^bb42
^bb42:
%311 = llvm.load %197 : !llvm.ptr -> i64
%312 = llvm.load %119 : !llvm.ptr -> i64
%313 = arith.constant 2 : i32
%315 = arith.extsi %313 : i32 to i64
%314 = arith.addi %312, %315 : i64
%316 = arith.cmpi sle, %311, %314 : i64
cf.cond_br %316, ^bb43, ^bb44
^bb43:
%317 = llvm.load %197 : !llvm.ptr -> i64
%318 = arith.constant 3 : i32
%320 = arith.extsi %318 : i32 to i64
%319 = arith.cmpi sge, %317, %320 : i64
cf.cond_br %319, ^bb45, ^bb46
^bb45:
%321 = llvm.load %115 : !llvm.ptr -> i64
%323 = arith.constant 1 : i32
%324 = llvm.load %197 : !llvm.ptr -> i64
%325 = llvm.load %197 : !llvm.ptr -> i64
%326 = arith.constant 1 : i32
%327 = arith.extsi %323 : i32 to i64
%328 = arith.extsi %326 : i32 to i64
%322 = func.call @windows(%327, %324, %325, %328) : (i64, i64, i64, i64) -> i64
%329 = arith.addi %321, %322 : i64
%330 = llvm.mlir.addressof @MOD : !llvm.ptr
%331 = llvm.load %330 : !llvm.ptr -> i64
%332 = arith.remsi %329, %331 : i64
llvm.store %332, %115 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%333 = llvm.load %115 : !llvm.ptr -> i64
%335 = arith.constant 1 : i32
%336 = llvm.load %197 : !llvm.ptr -> i64
%337 = llvm.load %197 : !llvm.ptr -> i64
%338 = arith.constant 0 : i32
%339 = arith.constant 1 : i32
%340 = arith.subi %338, %339 : i32
%341 = arith.extsi %335 : i32 to i64
%342 = arith.extsi %340 : i32 to i64
%334 = func.call @windows(%341, %336, %337, %342) : (i64, i64, i64, i64) -> i64
%343 = arith.addi %333, %334 : i64
%344 = llvm.mlir.addressof @MOD : !llvm.ptr
%345 = llvm.load %344 : !llvm.ptr -> i64
%346 = arith.remsi %343, %345 : i64
llvm.store %346, %115 : i64, !llvm.ptr
%347 = llvm.load %197 : !llvm.ptr -> i64
%348 = arith.constant 1 : i32
%350 = arith.extsi %348 : i32 to i64
%349 = arith.addi %347, %350 : i64
llvm.store %349, %197 : i64, !llvm.ptr
cf.br ^bb42
^bb44:
%351 = arith.constant 54 : i32
%352 = arith.extsi %351 : i32 to i64
%353 = llvm.mlir.constant(1 : i64) : i64
%354 = llvm.alloca %353 x i64 : (i64) -> !llvm.ptr
llvm.store %352, %354 : i64, !llvm.ptr
cf.br ^bb48
^bb48:
%355 = llvm.load %354 : !llvm.ptr -> i64
%356 = llvm.mlir.addressof @N : !llvm.ptr
%357 = llvm.load %356 : !llvm.ptr -> i64
%358 = arith.cmpi sle, %355, %357 : i64
cf.cond_br %358, ^bb49, ^bb50
^bb49:
%359 = llvm.load %115 : !llvm.ptr -> i64
%360 = arith.constant 1 : i32
%362 = arith.extsi %360 : i32 to i64
%361 = arith.addi %359, %362 : i64
%363 = llvm.mlir.addressof @MOD : !llvm.ptr
%364 = llvm.load %363 : !llvm.ptr -> i64
%365 = arith.remsi %361, %364 : i64
llvm.store %365, %115 : i64, !llvm.ptr
%366 = llvm.load %354 : !llvm.ptr -> i64
%367 = arith.constant 3 : i32
%369 = arith.extsi %367 : i32 to i64
%368 = arith.muli %366, %369 : i64
llvm.store %368, %354 : i64, !llvm.ptr
cf.br ^bb48
^bb50:
%371 = arith.constant 10 : i32
%372 = arith.constant 8 : i32
%373 = arith.extsi %371 : i32 to i64
%374 = arith.extsi %372 : i32 to i64
%370 = func.call @calloc(%373, %374) : (i64, i64) -> !llvm.ptr
%375 = arith.constant 6 : i32
%376 = arith.constant 0 : i32
%377 = arith.extsi %375 : i32 to i64
%378 = arith.extsi %376 : i32 to i64
%379 = llvm.getelementptr %370[%378] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %377, %379 : i64, !llvm.ptr
%380 = arith.constant 9 : i32
%381 = arith.constant 1 : i32
%382 = arith.extsi %380 : i32 to i64
%383 = arith.extsi %381 : i32 to i64
%384 = llvm.getelementptr %370[%383] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %382, %384 : i64, !llvm.ptr
%385 = arith.constant 9 : i32
%386 = arith.constant 2 : i32
%387 = arith.extsi %385 : i32 to i64
%388 = arith.extsi %386 : i32 to i64
%389 = llvm.getelementptr %370[%388] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %387, %389 : i64, !llvm.ptr
%390 = arith.constant 9 : i32
%391 = arith.constant 3 : i32
%392 = arith.extsi %390 : i32 to i64
%393 = arith.extsi %391 : i32 to i64
%394 = llvm.getelementptr %370[%393] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %392, %394 : i64, !llvm.ptr
%395 = arith.constant 12 : i32
%396 = arith.constant 4 : i32
%397 = arith.extsi %395 : i32 to i64
%398 = arith.extsi %396 : i32 to i64
%399 = llvm.getelementptr %370[%398] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %397, %399 : i64, !llvm.ptr
%400 = arith.constant 16 : i32
%401 = arith.constant 5 : i32
%402 = arith.extsi %400 : i32 to i64
%403 = arith.extsi %401 : i32 to i64
%404 = llvm.getelementptr %370[%403] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %402, %404 : i64, !llvm.ptr
%405 = arith.constant 16 : i32
%406 = arith.constant 6 : i32
%407 = arith.extsi %405 : i32 to i64
%408 = arith.extsi %406 : i32 to i64
%409 = llvm.getelementptr %370[%408] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %407, %409 : i64, !llvm.ptr
%410 = arith.constant 20 : i32
%411 = arith.constant 7 : i32
%412 = arith.extsi %410 : i32 to i64
%413 = arith.extsi %411 : i32 to i64
%414 = llvm.getelementptr %370[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %412, %414 : i64, !llvm.ptr
%415 = arith.constant 48 : i32
%416 = arith.constant 8 : i32
%417 = arith.extsi %415 : i32 to i64
%418 = arith.extsi %416 : i32 to i64
%419 = llvm.getelementptr %370[%418] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %417, %419 : i64, !llvm.ptr
%420 = arith.constant 60 : i32
%421 = arith.constant 9 : i32
%422 = arith.extsi %420 : i32 to i64
%423 = arith.extsi %421 : i32 to i64
%424 = llvm.getelementptr %370[%423] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %422, %424 : i64, !llvm.ptr
%425 = arith.constant 0 : i32
%426 = arith.extsi %425 : i32 to i64
llvm.store %426, %149 : i64, !llvm.ptr
cf.br ^bb51
^bb51:
%427 = llvm.load %149 : !llvm.ptr -> i64
%428 = arith.constant 10 : i32
%430 = arith.extsi %428 : i32 to i64
%429 = arith.cmpi slt, %427, %430 : i64
cf.cond_br %429, ^bb52, ^bb53
^bb52:
%432 = llvm.load %149 : !llvm.ptr -> i64
%433 = llvm.getelementptr %370[%432] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%431 = llvm.load %433 : !llvm.ptr -> i64
%434 = llvm.mlir.addressof @N : !llvm.ptr
%435 = llvm.load %434 : !llvm.ptr -> i64
%436 = arith.cmpi sle, %431, %435 : i64
cf.cond_br %436, ^bb54, ^bb55
^bb54:
%437 = llvm.load %115 : !llvm.ptr -> i64
%438 = arith.constant 1 : i32
%440 = arith.extsi %438 : i32 to i64
%439 = arith.addi %437, %440 : i64
%441 = llvm.mlir.addressof @MOD : !llvm.ptr
%442 = llvm.load %441 : !llvm.ptr -> i64
%443 = arith.remsi %439, %442 : i64
llvm.store %443, %115 : i64, !llvm.ptr
cf.br ^bb56
^bb55:
cf.br ^bb56
^bb56:
%444 = llvm.load %149 : !llvm.ptr -> i64
%445 = arith.constant 1 : i32
%447 = arith.extsi %445 : i32 to i64
%446 = arith.addi %444, %447 : i64
llvm.store %446, %149 : i64, !llvm.ptr
cf.br ^bb51
^bb53:
func.call @free(%370) : (!llvm.ptr) -> ()
%449 = llvm.mlir.addressof @str_0 : !llvm.ptr
%450 = llvm.load %115 : !llvm.ptr -> i64
%451 = llvm.call @printf(%449, %450) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
%452 = arith.constant 0 : i32
func.return %452 : i32
}
}