# 11315: 【原1315】frac1

### 题目描述

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

## Description

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

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

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

## Input Format

One line with a single integer N.

## Output Format

One fraction per line, sorted in order of magnitude.

## 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
``````

## q4x3's solution

``````/**
* 直接模拟
* 有序分数序列
**/
#include <iostream>

using namespace std;

int a[200][200];
double b[20000], c[200][200];

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

int main()
{
int j, N, p = 0;
double tmp;
bool flag;
cin >> N;
for (int i = 1; i <= N; ++ i) {
for (int j = 0; j <= i; ++ j) {
a[i][j] = j;
for (int k = 1; k <= j; ++ k) {
if ((j % k == 0) && (i % k == 0))
++p;
}
if (p != 1)
a[i][j] = 0;
p = 0;
b[(i + 2) * (i - 1) / 2 + j] = double(a[i][j]) / i;
c[i][j] = b[(i + 2) * (i - 1) / 2 + j];
}
}
mergeSort(1, (N + 3) * N / 2 + 1, b);
cout << "0/1" << endl;
for (int k = 0; k < (N + 3) * N / 2; ++ k)
for (int i = 1; i <= N; ++ i)
for (int j = 0; j <= i; ++ j)
if ((b[k] == c[i][j]) && (b[k] != 0))
cout << a[i][j] << '/' << i << endl;
cout << "1/1" << endl;
return 0;
}
``````

## victrid's solution

``````#include <iostream>
using namespace std;
int p[100001]   = {0};
int son[100001] = {0};
int mot[100001] = {0};
int main() {
//So simple?
int pl;
scanf("%d", &pl);
for (int i = 1; i <= pl; i++) {
for (int j = 0; j <= i; j++) {
int phs = j / (double)i * 100000;
if (p[phs] == 0) {
p[phs]   = 1;
son[phs] = j;
mot[phs] = i;
}
}
}
for (int i = 0; i <= 100000; i++) {
if (p[i] != 0) {
printf("%d/%d\n", son[i], mot[i]);
}
}
return 0;
}
``````

## yyong119's solution

``````#include<algorithm>
#include <iostream>

using namespace std;

struct Item {
double a;
double b;
}p[40000];

bool check(int a, int b) {
for (int i = 2; i <= min(a, b); i++)
if (a%i == 0 && b%i == 0)return false;
return true;
}

bool cmp(Item A, Item B) {
return A.a / A.b < B.a / B.b;
}

int main() {

ios::sync_with_stdio(false);
int n, t = 0;
cin >> n;
cout << "0/1" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j<i; j++) {
if (i % 2 == 0 && j % 2 == 0)continue;
if (check(i, j)) {
p[t].a = j; p[t++].b = i;
}
}
}
sort(p, p + t, cmp);
for (int i = 0; i < t; i++) cout << (int)p[i].a << "/" << (int)p[i].b << endl;
cout << "1/1" << endl;
return 0;
}
``````