usaco2.1.2-----orderd fractions（欧几里的）

/* ID:lvfuan11 PROG:frac1 LANG:C++ */ #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct Frac { double val; int up, down; Frac(int u, int d):up(u), down(d) {val = (double)up / (double)down;} bool operator < (const Frac& rhs) const { return val < rhs.val; } }; int n; vector<Frac> fv; int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); } int main() { freopen("frac1.in", "r", stdin); freopen("frac1.out", "w", stdout); while(~scanf("%d", &n)) { fv.clear(); for(int d = 1; d <= n; d++) { for(int u = 1; u < d; u++) if(gcd(d, u) == 1) { fv.push_back(Frac(u, d)); } } sort(fv.begin(), fv.end()); printf("0/1\n"); for(int i = 0; i < fv.size(); i++) printf("%d/%d\n", fv[i].up, fv[i].down); printf("1/1\n"); } return 0; }