题目描述
在社交媒体上, 经常会看到针对某一个观点同意与否的民意调查以及结果. 例如, 对某一观点表示支持的有 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', 中间用一个空格隔开, 表示化简后的比例.
输入输出样例
输入样例
1498 902 10
输出样例
5 3
说明
数据规模
对于 100% 的数据, 1≤A≤1000000,1≤B≤1000000,1≤L≤100,A/B≤L.
题解
l 很小, 所以可以直接枚举 a',b', 加上判断即可.
- #include<iostream>
- #include<algorithm>
- using namespace std;
- float a,b,l;
- float ans=100000000,bns=1;
- bool gcd(int a,int b)
- {
- if(a%b) return gcd(b,a%b);
- else if(b-1) return false;
- else return true;
- }
- int main()
- {
- cin>>a>>b>>l;
- for(float i=1;i<=l;i++)
- {
- for(float j=1;j<=l;j++)
- {
- if(gcd(i,j))
- {
- if(i/j>=a/b)
- {
- if(i/j<ans/bns)
- {
- ans=i;
- bns=j;
- }
- }
- }
- }
- }
- cout<<ans<<" "<<bns;
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-2945241.html