一個分數(shù)一般寫成兩個整數(shù)相除的形式：N/M，其中M不為0。最簡分數(shù)是指分子和分母沒有公約數(shù)的分數(shù)表示形式。
現(xiàn)給定兩個不相等的正分數(shù) N1/M1 和 N2/M2，要求你按從小到大的順序列出它們之間分母為K的最簡分數(shù)。
輸入格式：
輸入在一行中按N/M的格式給出兩個正分數(shù)，隨后是一個正整數(shù)分母K，其間以空格分隔。題目保證給出的所有整數(shù)都不超過1000。
輸出格式：
在一行中按N/M的格式列出兩個給定分數(shù)之間分母為K的所有最簡分數(shù)，按從小到大的順序，其間以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;}
新聞熱點
疑難解答
