C solutions for week 136

2 files changed, 80 insertions, 0 deletions

diff --git a/challenge-136/abigail/c/ch-1.c b/challenge-136/abigail/c/ch-1.c
new file mode 100644
index 0000000000..57acd46d89
--- /dev/null
+++ b/challenge-136/abigail/c/ch-1.c
@@ -0,0 +1,53 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file
+ */
+
+
+/*
+ * Find the GCD, using Stein's algorithm
+ *    (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
+ */
+long long gcd (long long u, long long v) {
+    long long u_odd = u % 2;
+    long long v_odd = v % 2;
+
+    return u == v || !v ? u
+         :           !u ? v
+         : !u_odd && !v_odd ? gcd (u >> 1, v >> 1) << 1
+         : !u_odd &&  v_odd ? gcd (u >> 1, v)
+         :  u_odd && !v_odd ? gcd (u,      v >> 1)
+         :  u     >   v     ? gcd (u - v,  v)
+         :                    gcd (v - u,  u);
+}
+
+
+int main (void) {
+    long long n, m;
+
+    while (scanf ("%lld %lld", &n, &m) == 2) {
+        long long ggcd = gcd (n, m);
+        short valid = 0;
+        /*
+         * Check whether ggcd is a power of 2
+         */
+        if (ggcd > 1) {
+            while (ggcd % 2 == 0) {
+                ggcd /= 2;
+            }
+            if (ggcd == 1) {
+                valid = 1;
+            }
+        }
+        printf ("%d\n", valid);
+    }
+
+    return (0);
+}
diff --git a/challenge-136/abigail/c/ch-2.c b/challenge-136/abigail/c/ch-2.c
new file mode 100644
index 0000000000..b5ef913ac9
--- /dev/null
+++ b/challenge-136/abigail/c/ch-2.c
@@ -0,0 +1,27 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file
+ */
+
+int count (long long target, long long this_fib, long long prev_fib) {
+    return target <  this_fib ? 0
+         : target == this_fib ? 1
+         : count (target - this_fib, this_fib + prev_fib, this_fib) +
+           count (target,            this_fib + prev_fib, this_fib);
+}
+
+int main (void) {
+    long long n;
+    while (scanf ("%lld", &n) == 1) {
+        printf ("%d\n", count (n, 1, 1));
+    }
+
+    return (0);
+}