Posted on 2009-03-25 18:39
superman 閱讀(104)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int gcd(int a, int b)
6 {
7 if (b == 0)
8 return a;
9 return gcd(b, a % b);
10 }
11
12 struct Fraction
13 {
14 int a, b;
15
16 bool isReducedFraction()
17 {
18 return gcd(a, b) == 1 ? true : false;
19 }
20 bool operator < (const Fraction & x) const
21 {
22 int t = b * x.b / gcd(b, x.b);
23 return t / b * a < t / x.b * x.a;
24 }
25 } frac[12800];
26
27 int main()
28 {
29 freopen("frac1.in", "r", stdin);
30 freopen("frac1.out", "w", stdout);
31
32 int n;
33
34 int cnt = 2;
35 frac[0].a = 0, frac[0].b = 1;
36 frac[1].a = 1, frac[1].b = 1;
37
38 cin >> n;
39 for (int b = 2; b <= n; b++)
40 for (int a = 1; a < b; a++)
41 if (gcd(a, b) == 1)
42 {
43 frac[cnt].a = a;
44 frac[cnt].b = b;
45 cnt++;
46 }
47
48 sort(frac, frac + cnt);
49
50 for (int i = 0; i < cnt; i++)
51 cout << frac[i].a << '/' << frac[i].b << endl;
52
53 return 0;
54 }
55