superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 2.1 - Ordered Fractions

Posted on 2009-03-25 18:39 superman 阅读(98) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理