1. 题目

PAT (Basic Level) Practice (中文): 1062

一个分数一般写成两个整数相除的形式:N/M,其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。
现给定两个不相等的正分数 N​1​​/M​1​​ 和 N​2​​/M​2​​,要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

1.1. 输入格式:

输入在一行中按 N/M 的格式给出两个正分数,随后是一个正整数分母 K,其间以空格分隔。题目保证给出的所有整数都不超过 1000。

1.2. 输出格式:

在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数,按从小到大的顺序,其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

1.3. 输入样例:

7/18 13/20 12

1.4. 输出样例:

5/12 7/12

2. 作答

2.1. 代码

#include "stdio.h"
int gcd(int a, int b){
    return b==0?a:gcd(b, a%b);
}

int main(int argc, char const *argv[]) {
    int i, n1, n2, m1, m2, k;
    int cout=0, begin, end;

    // 读入数据
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    if (n1*m2 > n2*m1) {
        n1^=n2; n2^=n1; n1^=n2;
        m1^=m2; m2^=m1; m1^=m2;
    }
    begin = n1 * k / m1 + 1;
    end   = n2 * k / m2;
    if ((n2 * k) % m2 == 0) --end;

    for (i = begin; i<=end; ++i){
        if (gcd(i, k)==1){
            if (cout) printf(" ");
            printf("%d/%d", i, k);
            cout = 1;
        }
    }

    return 0;
}

2.2. 评测结果

提交时间 状态 分数 题目 编译器 耗时 用户
2019/2/28 17:33:05 答案正确 20 1062 C (gcc) 3 ms soulans
测试点 结果 耗时 内存
0 答案正确 2 ms 352 KB
1 答案正确 3 ms 524 KB
2 答案正确 2 ms 256 KB
3 答案正确 2 ms 164 KB
4 答案正确 3 ms 616 KB

3. 标答

#include <iostream>
using namespace std;
//灰灰考研@一航代码
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    int n1, m1, n2, m2, k;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    if (n1 * m2 > n2 * m1)
    {
        swap(n1, n2);
        swap(m1, m2);
    }
    int num = 1;
    bool flag = false;
    while (n1 * k >= m1 * num)
        num++;
    while (n1 * k < m1 * num && m2 * num < n2 * k)
    {
        if (gcd(num, k) == 1)
        {
            printf("%s%d/%d", flag == true ? " " : "", num, k);
            flag = true;
        }
        num++;
    }
    return 0;
}