From 8482680ad68093fa56d10364f591764250c0c2f0 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Tue, 17 Apr 2018 16:34:59 +0800
Subject: 2.1 castle, frac1

---
 2.1/frac1.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
 create mode 100644 2.1/frac1.c

(limited to '2.1/frac1.c')

diff --git a/2.1/frac1.c b/2.1/frac1.c
new file mode 100644
index 0000000..1901abc
--- /dev/null
+++ b/2.1/frac1.c
@@ -0,0 +1,59 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: frac1
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+struct rational
+{
+	int numer, denom;
+};
+
+int comp(const void *s, const void *t)
+{
+	const struct rational *r1 = (struct rational*)s;
+	const struct rational *r2 = (struct rational*)t;
+	return r1->numer*r2->denom - r2->numer*r1->denom;
+}
+
+int gcd(int x, int y)
+{
+	if (y==0)
+		return x;
+	else
+		return gcd(y, x%y);
+}
+
+struct rational fracs[40000];
+int nfrac;
+
+int main()
+{
+	FILE *fin = fopen("frac1.in", "r");
+	FILE *fout = fopen("frac1.out", "w");
+
+	int N;
+	int i, j;
+	fscanf(fin, "%d", &N);
+	fclose(fin);
+
+	nfrac = 0;
+	for (i=1; i<=N; i++) {
+		for (j=1; j<i; j++) {
+			if (gcd(i, j)==1) {
+				fracs[nfrac].denom = i;
+				fracs[nfrac].numer = j;
+				nfrac++;
+			}
+		}
+	}
+	qsort(fracs, nfrac, sizeof(fracs[0]), comp);
+	fprintf(fout, "0/1\n");
+	for (i=0; i<nfrac; i++)
+		fprintf(fout, "%d/%d\n", fracs[i].numer, fracs[i].denom);
+	fprintf(fout, "1/1\n");
+	return 0;
+}
-- 
cgit v1.2.3