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

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

输入格式：

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

输出格式：

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

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

代码

测试点2未通过

#include<cstdio>
#include<algorithm>
using namespace std;
struct Fraction {  /* 分数结构体 */
    int up;        /* 分子 */
    int down;    /* 分母 */
};
int compare(Fraction ref, Fraction input) {
    Fraction reference, refInput;
    reference.up = ref.up * input.down;
    refInput.up = input.up * ref.down;
    if(reference.up > refInput.up)    return 666;
    else if(reference.up == refInput.up)  return 0;
    else  return -666;
}
int gcd(int m, int n) {
    if(m < n) {
        int temp = m;
        m = n;
        n = temp;
    }
    if(n == 0) return m;
    else return gcd(n, m % n);
}
int main() {
    Fraction fra1, fra2, answer;
    scanf("%d/%d %d/%d %d", &fra1.up, &fra1.down, &fra2.up, &fra2.down, &answer.down);
    /** Find out who is bigger and who is smaller */
    if(compare(fra1, fra2) > 0) {    // We think that fra2 is bigger
        swap(fra1.up, fra2.up);
        swap(fra1.down, fra2.down);
    }
    Fraction small, big;
    big.down = small.down = fra1.down * fra2.down;
    big.up = fra2.up * fra1.down;
    small.up = fra1.up * fra2.down;
    /** Find the length of answer */
    int length = 0;
    for(int i = 1; i <= answer.down; i++) {
        answer.up = i;
        if(compare(big, answer) > 0 && compare(small, answer) < 0 && gcd(answer.down, i) == 1)
            length++;
    }
    /** Display the result */
    bool spaceFlag = false;
    for(int i = 1; i <= answer.down; i++) {
        answer.up = i;
        if(compare(big, answer) > 0 && compare(small, answer) < 0 && gcd(answer.down, i) == 1) {
            printf("%s%d/%d", spaceFlag == true ? " " : "", i, answer.down);
            spaceFlag = true;
        }
    }
    return 0;
}