From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 math/cycleDetection.cpp | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 math/cycleDetection.cpp

(limited to 'math/cycleDetection.cpp')

diff --git a/math/cycleDetection.cpp b/math/cycleDetection.cpp
new file mode 100644
index 0000000..621af82
--- /dev/null
+++ b/math/cycleDetection.cpp
@@ -0,0 +1,16 @@
+void cycleDetection(ll x0, function<ll(ll)> f) {
+	ll a = x0, b = f(x0), length = 1;
+	for (ll power = 1; a != b; b = f(b), length++) {
+		if (power == length) {
+			power *= 2;
+			length = 0;
+			a = b;
+	}}
+	ll start = 0;
+	a = x0; b = x0;
+	for (ll i = 0; i < length; i++) b = f(b);
+	while (a != b) {
+		a = f(a);
+		b = f(b);
+		start++;
+}}
-- 
cgit v1.2.3