最简分数

题目描述：

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

思路:

题目解释：开始我题目都读不懂，我解释一下，把7/18转换成4.66/12，把13/20转换成7.8/12，就是求4.66到7.8之间的整数之间有无与12最大公因数为1的数

把先求出18，20，12三个数的最大公约数，把两个数转换成相同底，就是70/180，117/180，就是求70到117之间有无能被15（180/12）整除然后整除的数与12最大公因数为1.

注意区间为（70，117），边界取不到

代码:

#include<stdio.h>
#include<iostream>
using namespace std;
//求最大公因数 
int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
} 
//最大公约数 
int gcm(int a,int b){
	int c=gcd(a,b);
	return a*b/c; 
}
int main(){
	int a,b,c,e,d,j=0;
	int num[1000];
	scanf("%d/%d%d/%d%d",&a,&b,&c,&d,&e);
	int t=gcm(b,d);
	int t1=gcm(t,e);
	int g=t1/e;
	int first=t1/b*a;
	int last = t1/d*c;
	if (first>last){
		swap(first,last);
	}
	for(int i=first+1;i<last;i++){
		if (i%g==0){
			if(gcd(i/g,e)==1){
				num[j++]=i/g;
			}
		}
	}
	for(int i=0;i<j;i++){
		if(i==0){
			printf("%d/%d",num[i],e);
		}else{
			printf(" %d/%d",num[i],e);
		}
	}
	return 0;
}