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;
}