首页 > 试题广场 >

比例问题

[编程题]比例问题
  • 热度指数：3173 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
小强想要从中选出一个整数,从中选出一个整数 .使得满足  = 的同时且和的乘积最大。如果不存在这样的和,请输出“ 0 0”.

输入描述:
输入一行包含四个整数,,和.



输出描述:
输出两个整数表示满足条件的和.若不存在，则输出"0 0".
示例1

输入

1 1 2 1

输出

0 0
示例2

输入

1000 500 4 2

输出

1000 500
示例3

输入

1000 500 3 1

输出

999 333
算法知识视频讲解
开通博客
头像 小夏-求职中
发表于 2022-04-08 14:04:01
算法思路 先用辗转相除法求a与b的最大公约数，将a与b的比例化至最简， 然后在A->a与B->b中选择缩小的倍数最小的，该倍数乘以a和b即为答案 时间复杂度分析 该算法的时间复杂度为欧几里得算法的时间复杂度，为O(lg min(a,b))，是对数级别的 实现代码 #include 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 不想看论文
发表于 2022-03-26 16:02:10
A / B = a / b 可以转化为A * b = B * a，一开始的思路是：当左边大了就让A--，当右边大了就让B--，直到相等为止，但这样会有一个用例超时，然后改进了一下，让A或B直接一步到位，到达最可能相等的状态。比如左边大了，让A = B * a / b ，因为你通过很多次减减的操作最终 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
12条回答 6256浏览

热门推荐

通过挑战的用户

相关试题

比例问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号