# 11249: 【原1249】有序分数序列

### 题目描述

author: yixi 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1249

## Sample Input

``````5
``````

## Sample Output

``````0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
``````

## FineArtz's solution

``````/* 有序分数数列 */
#include <iostream>
using namespace std;

int a[10000] = {0}, b[10000] = {0};
double c[10000] = {0.0};

int gcd(int x, int y){
if (x % y == 0) return y;
return gcd(y, x % y);
}

inline void swap(int &x, int &y){ int t = x; x = y; y = t; }
inline void swap(double &x, double &y) { double t = x; x = y; y = t; }

void qsort(int low, int high){
if (low >= high) return;
int i = low, j = high, keya = a[i], keyb = b[i];
double key = c[i];
while (i < j){
while (i < j && c[j] >= key) --j;
a[i] = a[j];
b[i] = b[j];
c[i] = c[j];
while (i < j && c[i] <= key) ++i;
a[j] = a[i];
b[j] = b[i];
c[j] = c[i];
}
a[i] = keya;
b[i] = keyb;
c[i] = key;
qsort(i + 1, high);
qsort(low, j - 1);
}

int main(){
int n, cnt = 0;
cin >> n;
a[0] = 0;
b[0] = 1;
//cout << gcd(3, 2) << endl;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j){
if (gcd(i, j) == 1){
++cnt;
a[cnt] = j;
b[cnt] = i;
c[cnt] = double(j) / double(i);
}
}
qsort(1, cnt);
a[++cnt] = 1;
b[cnt] = 1;
c[cnt] = 1.0;
for (int i = 0; i <= cnt; ++i){
cout << a[i] << '/' << b[i] << endl;
}
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

bool visited[109][109] = { 0 };

class nums {
public:
int m = 0, n = 0;
double val = 0.0;
};

nums num[10009];

template <class T, class T_val = decltype(*declval<T>()),
class Compare = bool (*)(T_val, T_val)>
void quick_sort(T start, T end,
Compare cmp = [](T_val a, T_val b) {return a < b; }) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = *start;
for (bool status = true; i != j;) {
if (status) {
if (cmp(*j, key)) {
*i = *j;
++i;
status = false;
}
else
--j;
}
else {
if (cmp(key, *i)) {
*j = *i;
--j;
status = true;
}
else
++i;
}
}
*i = key;
//递归
quick_sort(start, ++i, cmp);
quick_sort(i, end, cmp);
}

int main() {
int n;
cin >> n;

int cnt = 0;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (visited[i][j])
continue;
//加入集合
num[cnt].m = i;
num[cnt].n = j;
num[cnt++].val = double(j) / double(i);

//访问其倍数
for (int k = 2; k * i <= n; ++k)
visited[k * i][k * j] = true;
}
}

//排序
quick_sort(num, num + cnt, [](nums a, nums b) {return a.val < b.val; });

//输出
printf("0/1\n");
for (int i = 0; i < cnt; ++i)
printf("%d/%d\n", num[i].n, num[i].m);
printf("1/1");

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Rational {
int a, b;
};

bool cmp(const Rational& a, const Rational& b) {
return a.a * b.b - a.b * b.a < 0;
}

int gcd(int a, int b) {
if (a < b) swap (a, b);
while (b > 0) {
int c = a % b;
a = b;
b = c;
}
return a;
}
int main() {
int N;
Rational data[10000];
int dN = 0;
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j < i; j++) {
if (gcd(i, j) == 1) {
data[dN].a = j;
data[dN++].b = i;
}
}
}
data[dN].a = 0; data[dN].b = 1; dN++;
data[dN].a = 1; data[dN].b = 1; dN++;
sort(data, data + dN, cmp);
for (int i = 0; i < dN; i++) {
printf("%d/%d\n", data[i].a, data[i].b);
}
return 0;
}
``````