← All problems Problem 730
Shifted Pythagorean Triples: S(100, 10^8) where P_k(n) counts primitive triples p^2 + q^2 + k = r^2 with 1 <= p <= q <= r and p + q + r <= n. Method: the Barning matrices preserve p^2 + q^2 - r^2 and gcd, so for each k the solutions form ternary trees over a finite set of small roots (a root has no positive perimeter-reducing parent: alpha = p+2q-2r, beta = 2p+q-2r, root iff alpha == 0 or beta == 0 or both negative). Scan roots with gcd(p,q,r) = 1, DFS each tree pruning on perimeter, count mirror trees once and double; unordered count per k is (ordered + [p == q nodes]) / 2.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(2^n)O(n)Space complexity O(n)O(1)Approach Flow solution Euclid parametrisation Verdict Suboptimal
Flow source
# Project Euler 730
# Shifted Pythagorean Triples: S(100, 10^8) where P_k(n) counts primitive
# triples p^2 + q^2 + k = r^2 with 1 <= p <= q <= r and p + q + r <= n.
# Method: the Barning matrices preserve p^2 + q^2 - r^2 and gcd, so for each
# k the solutions form ternary trees over a finite set of small roots (a root
# has no positive perimeter-reducing parent: alpha = p+2q-2r, beta = 2p+q-2r,
# root iff alpha == 0 or beta == 0 or both negative). Scan roots with
# gcd(p,q,r) = 1, DFS each tree pruning on perimeter, count mirror trees once
# and double; unordered count per k is (ordered + [p == q nodes]) / 2.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
function gcd(a: i64, b: i64) -> i64 {
let mut x: i64 = a
let mut y: i64 = b
while y != 0 {
let t: i64 = x % y
x = y
y = t
}
return x
}
# Count subtree nodes with perimeter <= n; ctr[0] = total, ctr[1] = p == q.
function dfs(p: i64, q: i64, r: i64, n: i64, ctr: ptr<i64>) -> void {
ctr[0] = ctr[0] + 1
if p == q {
ctr[1] = ctr[1] + 1
}
let pm1: i64 = 5 * (p - q) + 7 * r
if pm1 <= n {
let a: i64 = 2 * (p - q + r)
dfs(a - p, a + q, a + r, n, ctr)
}
let pm2: i64 = 5 * (p + q) + 7 * r
if pm2 <= n {
let t: i64 = 2 * (p + q + r)
dfs(t - p, t - q, t + r, n, ctr)
}
let pm3: i64 = 5 * (q - p) + 7 * r
if pm3 <= n {
let b: i64 = 2 * (q - p + r)
dfs(b + p, b - q, b + r, n, ctr)
}
return
}
function main() -> i32 {
let n: i64 = 100000000
let kmax: i64 = 100
let bmax: i64 = 600
let ord: ptr<i64> = calloc(kmax + 1, 8) as ptr<i64>
let eqc: ptr<i64> = calloc(kmax + 1, 8) as ptr<i64>
let ctr: ptr<i64> = calloc(2, 8) as ptr<i64>
# Roots have small coordinates (max seen 198 for k <= 100); scan p <= q.
for p in 1..(bmax + 1) {
let mut r: i64 = 1
for q in p..(bmax + 1) {
let s: i64 = p * p + q * q
while r * r < s {
r = r + 1
}
let mut rr: i64 = r
while rr * rr - s <= kmax {
let k: i64 = rr * rr - s
let alpha: i64 = p + 2 * q - 2 * rr
let beta: i64 = 2 * p + q - 2 * rr
let mut isroot: i64 = 0
if alpha == 0 || beta == 0 {
isroot = 1
}
if alpha < 0 && beta < 0 {
isroot = 1
}
if isroot == 1 && gcd(gcd(p, q), rr) == 1 && p + q + rr <= n {
ctr[0] = 0
ctr[1] = 0
dfs(p, q, rr, n, ctr)
if p < q {
ord[k] = ord[k] + 2 * ctr[0]
} else {
ord[k] = ord[k] + ctr[0]
eqc[k] = eqc[k] + ctr[1]
}
}
rr = rr + 1
}
}
}
let mut ans: i64 = 0
for k in 0..(kmax + 1) {
ans = ans + (ord[k] + eqc[k]) / 2
}
printf("%lld\n", ans)
free(ord as ptr<void>)
free(eqc as ptr<void>)
free(ctr as ptr<void>)
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 gcd_i64_i64(int64_t a, int64_t b);
void dfs_i64_i64_i64_i64_ptr_i64(int64_t p, int64_t q, int64_t r, int64_t n, int64_t* ctr);
int32_t main(void);
int64_t gcd_i64_i64(int64_t a, int64_t b) {
int64_t x = a;
int64_t y = b;
while (y != 0) {
int64_t t = FLOW_CHECKED_MOD((x), (y));
x = y;
y = t;
}
return x;
}
void dfs_i64_i64_i64_i64_ptr_i64(int64_t p, int64_t q, int64_t r, int64_t n, int64_t* ctr) {
ctr[0] = (ctr[0] + 1);
if (p == q) {
ctr[1] = (ctr[1] + 1);
}
int64_t pm1 = ((5 * (p - q)) + (7 * r));
if (pm1 <= n) {
int64_t a = (2 * ((p - q) + r));
dfs_i64_i64_i64_i64_ptr_i64((a - p), (a + q), (a + r), n, ctr);
}
int64_t pm2 = ((5 * (p + q)) + (7 * r));
if (pm2 <= n) {
int64_t t = (2 * ((p + q) + r));
dfs_i64_i64_i64_i64_ptr_i64((t - p), (t - q), (t + r), n, ctr);
}
int64_t pm3 = ((5 * (q - p)) + (7 * r));
if (pm3 <= n) {
int64_t b = (2 * ((q - p) + r));
dfs_i64_i64_i64_i64_ptr_i64((b + p), (b - q), (b + r), n, ctr);
}
return;
}
int32_t main(void) {
int64_t n = 100000000;
int64_t kmax = 100;
int64_t bmax = 600;
int64_t* ord = (int64_t*)(((int64_t*)(calloc((kmax + 1), 8))));
int64_t* eqc = (int64_t*)(((int64_t*)(calloc((kmax + 1), 8))));
int64_t* ctr = (int64_t*)(((int64_t*)(calloc(2, 8))));
int32_t __flow_step_1 = 1;
for (int32_t p = 1; (1 <= (bmax + 1)) ? p < (bmax + 1) : p > (bmax + 1); p += (1 <= (bmax + 1)) ? 1 : -1) {
int64_t r = 1;
int32_t __flow_step_2 = 1;
for (int32_t q = p; (p <= (bmax + 1)) ? q < (bmax + 1) : q > (bmax + 1); q += (p <= (bmax + 1)) ? 1 : -1) {
int64_t s = ((p * p) + (q * q));
while ((r * r) < s) {
r = (r + 1);
}
int64_t rr = r;
while (((rr * rr) - s) <= kmax) {
int64_t k = ((rr * rr) - s);
int64_t alpha = ((p + (2 * q)) - (2 * rr));
int64_t beta = (((2 * p) + q) - (2 * rr));
int64_t isroot = 0;
if ((alpha == 0 || beta == 0)) {
isroot = 1;
}
if ((alpha < 0 && beta < 0)) {
isroot = 1;
}
if (((isroot == 1 && gcd_i64_i64(gcd_i64_i64(p, q), rr) == 1) && ((p + q) + rr) <= n)) {
ctr[0] = 0;
ctr[1] = 0;
dfs_i64_i64_i64_i64_ptr_i64(p, q, rr, n, ctr);
if (p < q) {
ord[k] = (ord[k] + (2 * ctr[0]));
} else {
ord[k] = (ord[k] + ctr[0]);
eqc[k] = (eqc[k] + ctr[1]);
}
}
rr = (rr + 1);
}
}
}
int64_t ans = 0;
int32_t __flow_step_3 = 1;
for (int32_t k = 0; (0 <= (kmax + 1)) ? k < (kmax + 1) : k > (kmax + 1); k += (0 <= (kmax + 1)) ? 1 : -1) {
ans = (ans + FLOW_CHECKED_DIV(((ord[k] + eqc[k])), (2)));
}
printf("%lld\n", ans);
free(((void*)(ord)));
free(((void*)(eqc)));
free(((void*)(ctr)));
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 @gcd(%arg0: i64, %arg1: i64) -> 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.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb0:
%4 = llvm.load %3 : !llvm.ptr -> i64
%5 = arith.constant 0 : i32
%7 = arith.extsi %5 : i32 to i64
%6 = arith.cmpi ne, %4, %7 : i64
cf.cond_br %6, ^bb1, ^bb2
^bb1:
%8 = llvm.load %1 : !llvm.ptr -> i64
%9 = llvm.load %3 : !llvm.ptr -> i64
%10 = arith.remsi %8, %9 : i64
%11 = llvm.load %3 : !llvm.ptr -> i64
llvm.store %11, %1 : i64, !llvm.ptr
llvm.store %10, %3 : i64, !llvm.ptr
cf.br ^bb0
^bb2:
%12 = llvm.load %1 : !llvm.ptr -> i64
func.return %12 : i64
}
func.func @dfs(%arg0: i64, %arg1: i64, %arg2: i64, %arg3: i64, %arg4: !llvm.ptr) -> () {
%14 = arith.constant 0 : i32
%15 = arith.extsi %14 : i32 to i64
%16 = llvm.getelementptr %arg4[%15] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%13 = llvm.load %16 : !llvm.ptr -> i64
%17 = arith.constant 1 : i32
%19 = arith.extsi %17 : i32 to i64
%18 = arith.addi %13, %19 : i64
%20 = arith.constant 0 : i32
%21 = arith.extsi %20 : i32 to i64
%22 = llvm.getelementptr %arg4[%21] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %18, %22 : i64, !llvm.ptr
%23 = arith.cmpi eq, %arg0, %arg1 : i64
cf.cond_br %23, ^bb3, ^bb4
^bb3:
%25 = arith.constant 1 : i32
%26 = arith.extsi %25 : i32 to i64
%27 = llvm.getelementptr %arg4[%26] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%24 = llvm.load %27 : !llvm.ptr -> i64
%28 = arith.constant 1 : i32
%30 = arith.extsi %28 : i32 to i64
%29 = arith.addi %24, %30 : i64
%31 = arith.constant 1 : i32
%32 = arith.extsi %31 : i32 to i64
%33 = llvm.getelementptr %arg4[%32] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %29, %33 : i64, !llvm.ptr
cf.br ^bb5
^bb4:
cf.br ^bb5
^bb5:
%34 = arith.constant 5 : i32
%35 = arith.subi %arg0, %arg1 : i64
%37 = arith.extsi %34 : i32 to i64
%36 = arith.muli %37, %35 : i64
%38 = arith.constant 7 : i32
%40 = arith.extsi %38 : i32 to i64
%39 = arith.muli %40, %arg2 : i64
%41 = arith.addi %36, %39 : i64
%42 = arith.cmpi sle, %41, %arg3 : i64
cf.cond_br %42, ^bb6, ^bb7
^bb6:
%43 = arith.constant 2 : i32
%44 = arith.subi %arg0, %arg1 : i64
%45 = arith.addi %44, %arg2 : i64
%47 = arith.extsi %43 : i32 to i64
%46 = arith.muli %47, %45 : i64
%49 = arith.subi %46, %arg0 : i64
%50 = arith.addi %46, %arg1 : i64
%51 = arith.addi %46, %arg2 : i64
func.call @dfs(%49, %50, %51, %arg3, %arg4) : (i64, i64, i64, i64, !llvm.ptr) -> ()
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%52 = arith.constant 5 : i32
%53 = arith.addi %arg0, %arg1 : i64
%55 = arith.extsi %52 : i32 to i64
%54 = arith.muli %55, %53 : i64
%56 = arith.constant 7 : i32
%58 = arith.extsi %56 : i32 to i64
%57 = arith.muli %58, %arg2 : i64
%59 = arith.addi %54, %57 : i64
%60 = arith.cmpi sle, %59, %arg3 : i64
cf.cond_br %60, ^bb9, ^bb10
^bb9:
%61 = arith.constant 2 : i32
%62 = arith.addi %arg0, %arg1 : i64
%63 = arith.addi %62, %arg2 : i64
%65 = arith.extsi %61 : i32 to i64
%64 = arith.muli %65, %63 : i64
%67 = arith.subi %64, %arg0 : i64
%68 = arith.subi %64, %arg1 : i64
%69 = arith.addi %64, %arg2 : i64
func.call @dfs(%67, %68, %69, %arg3, %arg4) : (i64, i64, i64, i64, !llvm.ptr) -> ()
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%70 = arith.constant 5 : i32
%71 = arith.subi %arg1, %arg0 : i64
%73 = arith.extsi %70 : i32 to i64
%72 = arith.muli %73, %71 : i64
%74 = arith.constant 7 : i32
%76 = arith.extsi %74 : i32 to i64
%75 = arith.muli %76, %arg2 : i64
%77 = arith.addi %72, %75 : i64
%78 = arith.cmpi sle, %77, %arg3 : i64
cf.cond_br %78, ^bb12, ^bb13
^bb12:
%79 = arith.constant 2 : i32
%80 = arith.subi %arg1, %arg0 : i64
%81 = arith.addi %80, %arg2 : i64
%83 = arith.extsi %79 : i32 to i64
%82 = arith.muli %83, %81 : i64
%85 = arith.addi %82, %arg0 : i64
%86 = arith.subi %82, %arg1 : i64
%87 = arith.addi %82, %arg2 : i64
func.call @dfs(%85, %86, %87, %arg3, %arg4) : (i64, i64, i64, i64, !llvm.ptr) -> ()
cf.br ^bb14
^bb13:
cf.br ^bb14
^bb14:
func.return
}
func.func @main() -> i32 {
%88 = arith.constant 100000000 : i32
%89 = arith.extsi %88 : i32 to i64
%90 = arith.constant 100 : i32
%91 = arith.extsi %90 : i32 to i64
%92 = arith.constant 600 : i32
%93 = arith.extsi %92 : i32 to i64
%95 = arith.constant 1 : i32
%97 = arith.extsi %95 : i32 to i64
%96 = arith.addi %91, %97 : i64
%98 = arith.constant 8 : i32
%99 = arith.extsi %98 : i32 to i64
%94 = func.call @calloc(%96, %99) : (i64, i64) -> !llvm.ptr
%101 = arith.constant 1 : i32
%103 = arith.extsi %101 : i32 to i64
%102 = arith.addi %91, %103 : i64
%104 = arith.constant 8 : i32
%105 = arith.extsi %104 : i32 to i64
%100 = func.call @calloc(%102, %105) : (i64, i64) -> !llvm.ptr
%107 = arith.constant 2 : i32
%108 = arith.constant 8 : i32
%109 = arith.extsi %107 : i32 to i64
%110 = arith.extsi %108 : i32 to i64
%106 = func.call @calloc(%109, %110) : (i64, i64) -> !llvm.ptr
%111 = arith.constant 1 : i32
%112 = arith.constant 1 : i32
%114 = arith.extsi %112 : i32 to i64
%113 = arith.addi %93, %114 : i64
%115 = arith.index_cast %111 : i32 to index
%116 = arith.index_cast %113 : i32 to index
%118 = arith.constant 1 : index
%119 = arith.constant -1 : index
%120 = arith.cmpi sle, %115, %116 : index
%117 = arith.select %120, %118, %119 : index
cf.br ^bb15(%115 : index)
^bb15(%121: index):
%122 = arith.cmpi slt, %121, %116 : index
%123 = arith.cmpi sgt, %121, %116 : index
%124 = arith.select %120, %122, %123 : i1
cf.cond_br %124, ^bb16(%121 : index), ^bb17(%121 : index)
^bb16(%125: index):
%126 = arith.constant 1 : i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.mlir.constant(1 : i64) : i64
%129 = llvm.alloca %128 x i64 : (i64) -> !llvm.ptr
llvm.store %127, %129 : i64, !llvm.ptr
%130 = arith.constant 1 : i32
%132 = arith.extsi %130 : i32 to i64
%131 = arith.addi %93, %132 : i64
%133 = arith.index_cast %125 : i32 to index
%134 = arith.index_cast %131 : i32 to index
%136 = arith.constant 1 : index
%137 = arith.constant -1 : index
%138 = arith.cmpi sle, %133, %134 : index
%135 = arith.select %138, %136, %137 : index
cf.br ^bb18(%133 : index)
^bb18(%139: index):
%140 = arith.cmpi slt, %139, %134 : index
%141 = arith.cmpi sgt, %139, %134 : index
%142 = arith.select %138, %140, %141 : i1
cf.cond_br %142, ^bb19(%139 : index), ^bb20(%139 : index)
^bb19(%143: index):
%144 = arith.muli %125, %125 : index
%145 = arith.muli %143, %143 : index
%146 = arith.addi %144, %145 : index
%147 = arith.index_cast %146 : index to i64
cf.br ^bb21
^bb21:
%148 = llvm.load %129 : !llvm.ptr -> i64
%149 = llvm.load %129 : !llvm.ptr -> i64
%150 = arith.muli %148, %149 : i64
%151 = arith.cmpi slt, %150, %147 : i64
cf.cond_br %151, ^bb22, ^bb23
^bb22:
%152 = llvm.load %129 : !llvm.ptr -> i64
%153 = arith.constant 1 : i32
%155 = arith.extsi %153 : i32 to i64
%154 = arith.addi %152, %155 : i64
llvm.store %154, %129 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%156 = llvm.load %129 : !llvm.ptr -> i64
%157 = llvm.mlir.constant(1 : i64) : i64
%158 = llvm.alloca %157 x i64 : (i64) -> !llvm.ptr
llvm.store %156, %158 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%159 = llvm.load %158 : !llvm.ptr -> i64
%160 = llvm.load %158 : !llvm.ptr -> i64
%161 = arith.muli %159, %160 : i64
%162 = arith.subi %161, %147 : i64
%163 = arith.cmpi sle, %162, %91 : i64
cf.cond_br %163, ^bb25, ^bb26
^bb25:
%164 = llvm.load %158 : !llvm.ptr -> i64
%165 = llvm.load %158 : !llvm.ptr -> i64
%166 = arith.muli %164, %165 : i64
%167 = arith.subi %166, %147 : i64
%168 = arith.constant 2 : i32
%170 = arith.index_cast %143 : index to i32
%169 = arith.muli %168, %170 : i32
%172 = arith.index_cast %125 : index to i32
%171 = arith.addi %172, %169 : i32
%173 = arith.constant 2 : i32
%174 = llvm.load %158 : !llvm.ptr -> i64
%176 = arith.extsi %173 : i32 to i64
%175 = arith.muli %176, %174 : i64
%178 = arith.extsi %171 : i32 to i64
%177 = arith.subi %178, %175 : i64
%179 = arith.constant 2 : i32
%181 = arith.index_cast %125 : index to i32
%180 = arith.muli %179, %181 : i32
%183 = arith.index_cast %143 : index to i32
%182 = arith.addi %180, %183 : i32
%184 = arith.constant 2 : i32
%185 = llvm.load %158 : !llvm.ptr -> i64
%187 = arith.extsi %184 : i32 to i64
%186 = arith.muli %187, %185 : i64
%189 = arith.extsi %182 : i32 to i64
%188 = arith.subi %189, %186 : i64
%190 = arith.constant 0 : i32
%191 = arith.extsi %190 : i32 to i64
%192 = llvm.mlir.constant(1 : i64) : i64
%193 = llvm.alloca %192 x i64 : (i64) -> !llvm.ptr
llvm.store %191, %193 : i64, !llvm.ptr
%194 = arith.constant 0 : i32
%196 = arith.extsi %194 : i32 to i64
%195 = arith.cmpi eq, %177, %196 : i64
%197 = scf.if %195 -> (i1) {
%198 = arith.constant true
scf.yield %198 : i1
} else {
%199 = arith.constant 0 : i32
%201 = arith.extsi %199 : i32 to i64
%200 = arith.cmpi eq, %188, %201 : i64
scf.yield %200 : i1
}
cf.cond_br %197, ^bb27, ^bb28
^bb27:
%202 = arith.constant 1 : i32
%203 = arith.extsi %202 : i32 to i64
llvm.store %203, %193 : i64, !llvm.ptr
cf.br ^bb29
^bb28:
cf.br ^bb29
^bb29:
%204 = arith.constant 0 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.cmpi slt, %177, %206 : i64
%207 = scf.if %205 -> (i1) {
%208 = arith.constant 0 : i32
%210 = arith.extsi %208 : i32 to i64
%209 = arith.cmpi slt, %188, %210 : i64
scf.yield %209 : i1
} else {
%211 = arith.constant false
scf.yield %211 : i1
}
cf.cond_br %207, ^bb30, ^bb31
^bb30:
%212 = arith.constant 1 : i32
%213 = arith.extsi %212 : i32 to i64
llvm.store %213, %193 : i64, !llvm.ptr
cf.br ^bb32
^bb31:
cf.br ^bb32
^bb32:
%214 = llvm.load %193 : !llvm.ptr -> i64
%215 = arith.constant 1 : i32
%217 = arith.extsi %215 : i32 to i64
%216 = arith.cmpi eq, %214, %217 : i64
%218 = scf.if %216 -> (i1) {
%221 = arith.index_cast %125 : index to i64
%222 = arith.index_cast %143 : index to i64
%220 = func.call @gcd(%221, %222) : (i64, i64) -> i64
%223 = llvm.load %158 : !llvm.ptr -> i64
%219 = func.call @gcd(%220, %223) : (i64, i64) -> i64
%224 = arith.constant 1 : i32
%226 = arith.extsi %224 : i32 to i64
%225 = arith.cmpi eq, %219, %226 : i64
scf.yield %225 : i1
} else {
%227 = arith.constant false
scf.yield %227 : i1
}
%228 = scf.if %218 -> (i1) {
%229 = arith.addi %125, %143 : index
%230 = llvm.load %158 : !llvm.ptr -> i64
%232 = arith.index_cast %229 : index to i32
%233 = arith.trunci %230 : i64 to i32
%231 = arith.addi %232, %233 : i32
%235 = arith.extsi %231 : i32 to i64
%234 = arith.cmpi sle, %235, %89 : i64
scf.yield %234 : i1
} else {
%236 = arith.constant false
scf.yield %236 : i1
}
cf.cond_br %228, ^bb33, ^bb34
^bb33:
%237 = arith.constant 0 : i32
%238 = arith.constant 0 : i32
%239 = arith.extsi %237 : i32 to i64
%240 = arith.extsi %238 : i32 to i64
%241 = llvm.getelementptr %106[%240] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %239, %241 : i64, !llvm.ptr
%242 = arith.constant 0 : i32
%243 = arith.constant 1 : i32
%244 = arith.extsi %242 : i32 to i64
%245 = arith.extsi %243 : i32 to i64
%246 = llvm.getelementptr %106[%245] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %244, %246 : i64, !llvm.ptr
%248 = llvm.load %158 : !llvm.ptr -> i64
%249 = arith.index_cast %125 : index to i64
%250 = arith.index_cast %143 : index to i64
func.call @dfs(%249, %250, %248, %89, %106) : (i64, i64, i64, i64, !llvm.ptr) -> ()
%251 = arith.cmpi slt, %125, %143 : index
cf.cond_br %251, ^bb36, ^bb37
^bb36:
%253 = llvm.getelementptr %94[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%252 = llvm.load %253 : !llvm.ptr -> i64
%254 = arith.constant 2 : i32
%256 = arith.constant 0 : i32
%257 = arith.extsi %256 : i32 to i64
%258 = llvm.getelementptr %106[%257] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%255 = llvm.load %258 : !llvm.ptr -> i64
%260 = arith.extsi %254 : i32 to i64
%259 = arith.muli %260, %255 : i64
%261 = arith.addi %252, %259 : i64
%262 = llvm.getelementptr %94[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %261, %262 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
%264 = llvm.getelementptr %94[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%263 = llvm.load %264 : !llvm.ptr -> i64
%266 = arith.constant 0 : i32
%267 = arith.extsi %266 : i32 to i64
%268 = llvm.getelementptr %106[%267] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%265 = llvm.load %268 : !llvm.ptr -> i64
%269 = arith.addi %263, %265 : i64
%270 = llvm.getelementptr %94[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %269, %270 : i64, !llvm.ptr
%272 = llvm.getelementptr %100[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%271 = llvm.load %272 : !llvm.ptr -> i64
%274 = arith.constant 1 : i32
%275 = arith.extsi %274 : i32 to i64
%276 = llvm.getelementptr %106[%275] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%273 = llvm.load %276 : !llvm.ptr -> i64
%277 = arith.addi %271, %273 : i64
%278 = llvm.getelementptr %100[%167] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %277, %278 : i64, !llvm.ptr
cf.br ^bb38
^bb38:
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%279 = llvm.load %158 : !llvm.ptr -> i64
%280 = arith.constant 1 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.addi %279, %282 : i64
llvm.store %281, %158 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%283 = arith.addi %143, %135 : index
cf.br ^bb18(%283 : index)
^bb20(%284: index):
%285 = arith.addi %125, %117 : index
cf.br ^bb15(%285 : index)
^bb17(%286: index):
%287 = arith.constant 0 : i32
%288 = arith.extsi %287 : i32 to i64
%289 = llvm.mlir.constant(1 : i64) : i64
%290 = llvm.alloca %289 x i64 : (i64) -> !llvm.ptr
llvm.store %288, %290 : i64, !llvm.ptr
%291 = arith.constant 0 : i32
%292 = arith.constant 1 : i32
%294 = arith.extsi %292 : i32 to i64
%293 = arith.addi %91, %294 : i64
%295 = arith.index_cast %291 : i32 to index
%296 = arith.index_cast %293 : i32 to index
%298 = arith.constant 1 : index
%299 = arith.constant -1 : index
%300 = arith.cmpi sle, %295, %296 : index
%297 = arith.select %300, %298, %299 : index
cf.br ^bb39(%295 : index)
^bb39(%301: index):
%302 = arith.cmpi slt, %301, %296 : index
%303 = arith.cmpi sgt, %301, %296 : index
%304 = arith.select %300, %302, %303 : i1
cf.cond_br %304, ^bb40(%301 : index), ^bb41(%301 : index)
^bb40(%305: index):
%306 = llvm.load %290 : !llvm.ptr -> i64
%308 = arith.index_cast %305 : index to i64
%309 = llvm.getelementptr %94[%308] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%307 = llvm.load %309 : !llvm.ptr -> i64
%311 = arith.index_cast %305 : index to i64
%312 = llvm.getelementptr %100[%311] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%310 = llvm.load %312 : !llvm.ptr -> i64
%313 = arith.addi %307, %310 : i64
%314 = arith.constant 2 : i32
%316 = arith.extsi %314 : i32 to i64
%315 = arith.divsi %313, %316 : i64
%317 = arith.addi %306, %315 : i64
llvm.store %317, %290 : i64, !llvm.ptr
%318 = arith.addi %305, %297 : index
cf.br ^bb39(%318 : index)
^bb41(%319: index):
%320 = llvm.mlir.addressof @str_0 : !llvm.ptr
%321 = llvm.load %290 : !llvm.ptr -> i64
%322 = llvm.call @printf(%320, %321) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%94) : (!llvm.ptr) -> ()
func.call @free(%100) : (!llvm.ptr) -> ()
func.call @free(%106) : (!llvm.ptr) -> ()
%326 = arith.constant 0 : i32
func.return %326 : i32
}
}