题目描述

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

输入格式

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

输出格式

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

分析

  1. 注意读题，是两个分数之间的以k为分母且最简的分数。
  2. 题目有意降低难度，即在题目中告知我们要用最大公约数知识

    数学——最大公约数与最小公倍数

    最大公约数

  3. 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
  4. 如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。

最小公倍数

  1. 两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
  2. 设a,b分别为两个数，ab = a和b的最大公约数 a和b的最小公倍数

参考代码

#include <bits/stdc++.h>
using namespace std;
int GCD(int a,int b)
{
    return a%b?GCD(b,a%b):b;
}
int main() {
    int n1, m1, n2, m2, k;
    int *p, *q;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    //qujian
    if(n1*m2 > n2 *m1)
    {
        int a ,b ;
        a = n1 ; b = m1 ;

        n1 = n2 ; m1 = m2 ;
        n2 = a  ; m2 = b ;
    }
    int cnt = 0 ;
    for(int i = 1 ; i*m2 < k*n2 ; ++i)
    {
        if( i * m1 <= k*n1)
        {
            continue;
        }

        if(GCD(k,i) != 1)
        {
            continue;
        }

        if(i * m1 > k*n1)
        {
            ++cnt;
        }
        if(cnt > 1)
        {
            cout<<" ";
        }
        printf("%d/%d",i,k);

    }
    return 0;
}

谢谢访问