1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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;
}
|
