【题目描述】
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 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’}{B’}$ 有一些特殊要求，是这个题的解题关键。
3. 化简后的A’和B’都要小于 L， 而且要互质（互质可以用最大公约数来解决）
4. 要求$\frac{A’}{B’}$ >= $\frac{A}{B}$ ，化简后的值要大于等于化简前的值。根据十字相乘法就是 A’B >= B’A ,移项得 A’B – B’A >= 0。
5. 如果要用除法计算的话， 一定要注意用double数据类型。
6. 题目要 $\frac{A’}{B’}$ –$\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;
}返回目录：NOIP/CSP信息学奥赛复赛