【题目描述】

在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为1498:902。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1）的前提下，A’/B’ ≥ A/B且 A’/B’ – A/B 的值尽可能小。

【输入描述】

输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。

【输出描述】

输出共一行，包含两个整数 A’，B’，中间用一个空格隔开，表示化简后的比例。

【输入样例1】

1498 902 10

【输出样例1】

5 3

【数据说明】

对于 100%的数据，1  ≤  A  ≤  1,000,000，1  ≤  B  ≤  1,000,000，1  ≤  L  ≤  100， A/B  ≤  L。

【分析】

1.题目中的数据范围不大，特别是L的范围，上限是100，可以暴力枚举。

2.题目中$\frac{A}{B}$ 化简后的$\frac{A^{\prime }}{B^{\prime }}$ 有一些特殊要求，是这个题的解题关键。

3. 化简后的A’和B’都要小于 L， 而且要互质（互质可以用最大公约数来解决）

4. 要求$\frac{A^{\prime }}{B^{\prime }}$ >= $\frac{A}{B}$ ，化简后的值要大于等于化简前的值。根据十字相乘法就是 A’B >= B’A ,移项得 A’B – B’A >= 0。

5. 如果要用除法计算的话， 一定要注意用double数据类型。

6. 题目要 $\frac{A^{\prime }}{B^{\prime }}$ –$\frac{A}{B}$ 要尽可能的小，这个就可以直接枚举 A’ 和 B’ , 这个稍微麻烦点，可以根据上面的符合条件的数据，利用十字相乘的公式计算A’B-B’A的最小值。

【解题思路1】

A’和B’ 从1开始枚举，在L的范围内，用条件限制，等循环结束后，取最后一次的值即可。

【参考代码1】

#include<cstdio>  #include<iostream>   using namespace std;  int gcd(int a,int b)   //辗转相除法求最大公约数    {        if(a%b==0)           return b;       else           return gcd(b,a%b);   }  int main()  {  	int A,B,L; //定义分子，分母，限定范围  	int AA,BB; //定义经过比较后的最小的符合条件的分子分母   	int min=1000001; //定义最小值   	scanf("%d%d%d",&A,&B,&L); //读入分子，分母，限定范围    	for(int i=1;i<=L;i++)  //枚举分子 ，就是A'   	 for(int j=1;j<=L;j++)  //枚举分母 ，就是B'   		{  			if(gcd(i,j)==1 && (i*B>=j*A))   			//这个if分别限制了分子分母互质，化简后的值要大于化简前的值  			{  				int temp = i*B-j*A;  //用temp表示当前符合要求的数据，然后求差   				if(temp < min)  //进行差的比较,符合条件的进行赋值，每次取最小   				{  					AA=i;  					BB=j;  					min=temp;	   				}   			}  		}   	printf("%d %d",AA,BB);  	return 0;   	  }

(adsbygoogle = window.adsbygoogle || []).push({});