PAT Basic 1062. 最简分数

1. 题目描述：

一个分数一般写成两个整数相除的形式：\(N/M\)，其中 \(M\) 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 \(N_1/M_1\) 和 \(N_2/M_2\)，要求你按从小到大的顺序列出它们之间分母为 \(K\) 的最简分数。

2. 输入格式：

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

3. 输出格式：

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

4. 输入样例：

7/18 13/20 12

5. 输出样例：

5/12 7/12

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

关键在于最简分数的判断，一个分数为最简分数等价于分子分母的最大公约数为1。这里定义子函数int getGCD(int num1, int num2);使用辗转相除法求两数的最大公约数。然后根据\(N_1,N_2,M_1,M_2\)和\(K\)计算出分子的上下限，注意到题目中要求最简分数在给定两数之间，这里使用库函数ceil和floor分别计算上下限，最后遍历上下限输出结果。

第一次提交时testpoint1，2报wrong answer，检查了逻辑感觉无问题，参考大佬题解：1062. 最简分数(20)-PAT乙级真题_柳婼的博客-CSDN博客 ，发现固定思维了，给定的两个分数不一定是按照大小顺序给出，需要自己判断下。。。修改后testpoint2仍然报wrong answer。最后发现还是上下限的问题，即使用了ceil和floor还是有可能出现最简分数与给定的两个分数相等的情况，这里还需要额外判断下，确保最简分数一定在两数之间，修改后AC。

My Code:

#include <stdio.h>
#include <math.h> // floor ceil header

int getGCD(int num1, int num2);

// first submit testpoint1, 2 wrong answer
int main(void)
{
    int num1=0, den1=0; // numerator1 denominator1
    int num2=0, den2=0;
    int den3=0;
    int lowBound=0, upBound=0;
    int i=0; // iterator
    int firstBlood=0; // output space flag
    int temp=0; // to swap fractions
    
    scanf("%d/%d", &num1, &den1);
    scanf("%d/%d", &num2, &den2);
    scanf("%d", &den3);
    
    //fixed testpoint1, testpoint2 still wrong answer
    if(num1*den2 > num2*den1) // N1/M1 may > N2/M2, need to swap two fractions
    {
        temp = num1;
        num1 = num2;
        num2 = temp;
        
        temp = den1;
        den1 = den2;
        den2 = temp;
    }
    
    //printf("GCD of (1997, 615): %d\n", getGCD(1997, 615)); // test getGCD
    //printf("GCD of (2, 7): %d\n", getGCD(2, 7)); // test getGCD
    
    // num1/den1 < x/den3 < num2/den2
//     lowBound = ceil(1.0*num1*den3/den1);
//     upBound = floor(1.0*num2*den3/den2);
    lowBound = ceil((double)num1*(double)den3/(double)den1);
    upBound = floor((double)num2*(double)den3/(double)den2);
    
    // fixed testpoint2, it's about bound bug.
    if(num1 * den3 == lowBound * den1) ++lowBound;
    if(num2 * den3 == upBound * den2) --upBound;
    
    for(i=lowBound; i<=upBound; ++i)
    {
        if(getGCD(i, den3)==1) // GCD == 1 means no other divisor
        {
            if(firstBlood)
            {
                printf(" %d/%d", i, den3);
            }
            else
            {
                firstBlood = 1;
                printf("%d/%d", i, den3);
            }
        }
    }
    printf("\n");
    
    return 0;
}

int getGCD(int num1, int num2)// GCD: Greatest Common Divisor
{
    int temp =0;
    while((temp=num1%num2) != 0)
    {
        num1 = num2;
        num2 = temp;
    }
    
    return num2;
}