From f54a9727f09e0ffe52f4123ed3f9e0cd67ddcff9 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Tue, 29 May 2018 21:05:53 +0800
Subject: 69, 71, 81

---
 euler69.c | 41 +++++++++++++++++++++++++++++++++++++++++
 euler71.c | 39 +++++++++++++++++++++++++++++++++++++++
 euler81.c | 28 ++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
 create mode 100644 euler69.c
 create mode 100644 euler71.c
 create mode 100644 euler81.c

diff --git a/euler69.c b/euler69.c
new file mode 100644
index 0000000..e95a6c2
--- /dev/null
+++ b/euler69.c
@@ -0,0 +1,41 @@
+#include <stdio.h>
+
+int euler_phi(int n)
+{
+	int phi = n;
+
+	if (n % 2 == 0) {
+		while (n % 2 == 0)
+			n /= 2;
+		phi /= 2;
+	}
+
+	for (int i = 3; i*i <= n; i++) {
+		if (n % i == 0) {
+			while (n % i == 0)
+				n /= i;
+			phi /= i;
+			phi *= (i-1);
+		}
+	}
+
+	if (n > 1)
+		phi = phi / n * (n-1);
+
+	return phi;
+}
+
+int main()
+{
+	int res;
+	double max_n_div_phi = 0;
+	for (int i = 2; i <= 1000000; i++) {
+		double n_div_phi = (double)i / euler_phi(i);
+		if (n_div_phi > max_n_div_phi) {
+			res = i;
+			max_n_div_phi = n_div_phi;
+		}
+	}
+
+	printf("%d\n", res);
+}
diff --git a/euler71.c b/euler71.c
new file mode 100644
index 0000000..7a802c5
--- /dev/null
+++ b/euler71.c
@@ -0,0 +1,39 @@
+#include <stdio.h>
+
+int gcd(int x, int y)
+{
+	if (x == 0)
+		return y;
+	else
+		return gcd(y%x, x);
+}
+
+void imm_left(int numer, int denom, int max_denom, int *nu, int *de)
+{
+	/* nu/de < numer/denom
+	 * => nu < numer*de/denom
+	 */
+	int res_nu = 0, res_de = 1;
+	int i;
+	for (i = 2; i <= max_denom; i++) {
+		if (i == denom)
+			continue;
+		int t = numer * i / denom;
+		/* t/i > res_nu/res_de */
+		if (gcd(t, i) != 1)
+			continue;
+		if (t * res_de > i * res_nu) {
+			res_nu = t;
+			res_de = i;
+		}
+	}
+	*nu = res_nu;
+	*de = res_de;
+}
+
+int main()
+{
+	int nu, de;
+	imm_left(3, 7, 1000000, &nu, &de);
+	printf("%d/%d\n", nu, de);
+}
diff --git a/euler81.c b/euler81.c
new file mode 100644
index 0000000..8303800
--- /dev/null
+++ b/euler81.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+
+int main()
+{
+	int m[80][80];
+
+	for (int i = 0; i < 80; i++) {
+		for (int j = 0; j < 80; j++) {
+			scanf("%d", &m[i][j]);
+		}
+	}
+
+	for (int i = 1; i < 80; i++) {
+		m[0][i] = m[0][i-1] + m[0][i];
+	}
+
+	for (int i = 1; i < 80; i++) {
+		m[i][0] = m[i-1][0] + m[i][0];
+		for (int j = 1; j < 80; j++) {
+			if (m[i-1][j] < m[i][j-1])
+				m[i][j] = m[i-1][j] + m[i][j];
+			else
+				m[i][j] = m[i][j-1] + m[i][j];
+		}
+	}
+
+	printf("%d\n", m[79][79]);
+}
-- 
cgit v1.2.3