题目描述

一个分数一般写成两个整数相除的形式: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;
}

谢谢访问