最简分数


题目描述

一个分数一般写成两个整数相除的形式:N/M,其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。
现给定两个不相等的正分数 N1/M1和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是约数。

    img

最小公倍数

  1. 两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

  2. 设a,b分别为两个数,a

    b = a和b的最大公约数

    a和b的最小公倍数

    img

参考代码

#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;
}

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
 上一篇
地图分析 地图分析
题目描述你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆
下一篇 
朋友数 朋友数
题目描述如果两个整数各位数字的和是一样的,则被称为是“朋友数”,而那个公共的和就是它们的“朋友证号”。例如 123 和 51 就是朋友数,因为 1+2+3 = 5+1 = 6,而 6 就是它们的朋友证号。给定一些整数,要求你统计一下它们中有
2021-07-17
  目录