1062 最简分数 (20 分)

原题

https://pintia.cn/problem-sets/994805260223102976/problems/994805268334886912

思路

也是参看的别人的代码。记录下三个要点。

1、输入的两个分数不是按大小排序，自已要判断一下

2、怎么判断分子和分母不能再约分？

这两个数之间没有公约数——即最大公约数是1。

// 辗转相除法求两个非负整数的最大公约数
int gcd(int x, int y){
    return y==0?x:gcd(y,x%y);
}

3、结果是开区间，不等于N1?/M1? 和 N2?/M2

代入测试用例：1/12 11/12 12 输出：5/12 7/12

代码

#include 
using namespace std;

// 辗转相除法求两个非负整数的最大公约数
int gcd(int x, int y){
    return y==0?x:gcd(y,x%y);//返回最大公约数
}
int main(void){
    int N1,M1,N2,M2,K;
    scanf("%d/%d %d/%d %d",&N1,&M1,&N2,&M2,&K);
    if(N1*M2>N2*M1){//自己确定最小最大值
        swap(N1,N2);
        swap(M1,M2);
    } 
    
    int small=(N1*K)/M1;
    int max=(N2*K)/M2;
    (N2*K)%M2>0?max++:max;//开区间

    bool flag=false;
    for (int i =small+1; i < max; i++)//开区间
    {
        if(gcd(i,K)==1){ //最大公约数为1就代表分子和分母不能再约分
           printf("%s%d/%d",flag?" ":"",i,K);
           flag=true;
        }     
    }
}

大佬的代码更好

#include 
using namespace std;
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    int n1, m1, n2, m2, k;
    scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k);
    if(n1 * m2 > n2 * m1) {
        swap(n1, n2);
        swap(m1, m2);
    }
    int num = 1;
    bool flag = false;
    while(n1 * k >= m1 * num) num++;
    while(n1 * k < m1 * num && m2 * num < n2 * k) {
        if(gcd(num, k) == 1) {
            printf("%s%d/%d", flag == true ? " " : "", num, k);
            flag = true;
        }
        num++;
    }
    return 0;
}