USACO Section 2.1: Ordered Fractions
6777 ワード
1 /*
2 ID: leetcod3
3 PROG: frac1
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <queue>
14 #include <cmath>
15 #include <list>
16 #include <cstring>
17 #include <cstdlib>
18 #include <limits>
19 #include <stack>
20
21 using namespace std;
22
23 ofstream fout ("frac1.out");
24 ifstream fin ("frac1.in");
25
26 int N;
27
28 int main()
29 {
30 fin >> N;
31 set<pair<int, int> > S, T;
32 for (int i = 1; i <= N; ++i) {
33 for (int j = 1; j <= i; ++j) {
34 if (S.find(make_pair(j, i)) == S.end()) {
35 T.insert(make_pair(j, i));
36 S.insert(make_pair(j, i));
37 int k = 2;
38 while (k * i <= N) {
39 S.insert(make_pair(j*k, i*k));
40 k++;
41 }
42 }
43 }
44 }
45 T.insert(make_pair(0, 1));
46 map<double, pair<int, int> > H;
47 for (set<pair<int, int> >::iterator it = T.begin(); it != T.end(); it++) {
48 pair<int, int> tmp = *it;
49 H[(double)tmp.first*1.0/(tmp.second*1.0)] = tmp;
50 }
51 for (map<double, pair<int, int> >::iterator it = H.begin(); it != H.end(); it++)
52 fout << (it->second).first << "/" << (it->second).second << endl;
53 return 0;
54 }