diff options
Diffstat (limited to '2.1/frac1.c')
-rw-r--r-- | 2.1/frac1.c | 59 |
1 files changed, 59 insertions, 0 deletions
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; +} |