1062. 最简分数(20)

2019-11-11 06:54:40

字体：大中小

来源：转载

供稿：网友

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

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

输入格式：

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

输出格式：

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

输入样例： 7/18 13/20 12 输出样例： 5/12 7/12

#include <iostream>#include <cstdio>using namespace std;int GCD(int a , int b){ int gcd; while( b!= 0){ gcd = a % b; a = b ; b = gcd; } gcd = a; return gcd;}int GCM(int a , int b){ int tmp1 = a; int tmp2 = b; int gcd = GCD(tmp1,tmp2); int gcm = a * b / gcd; return gcm; }int main(){ int A,B,C,D; int num; scanf("%d/%d %d/%d %d",&A,&B,&C,&D,&num); int tmp1 = GCM(B,D); int gcm = GCM(tmp1,num); int mul = gcm / num; int start = A * gcm / B; int end = C * gcm / D; int cnt = 0; int Fenzi[num]; if ( start > end){ start = start + end; end = start - end; start = start - end; } for ( int i = 1 ; i < num ; i++){ int tmp = i * mul; if ( GCD(i,num) == 1 && tmp > start && tmp < end){ Fenzi[cnt++] = i; } } cout<<Fenzi[0]<<"/"<<num; for ( int i = 1 ; i < cnt ; i++){ cout<<" "<<Fenzi[i]<<"/"<<num; } return 0;}

这里写图片描述