首页 > 试题广场 >

比例问题

[编程题]比例问题
  • 热度指数：3100 时间限制：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
算法知识视频讲解
添加回答
O_n2头像 O_n2
其实是一个求最大公约数的问题 
def simplify(a, b):
    m, n = a, b
    while n > 0:
        m, n = n, m % n
    return a // m, b // m
 
 
def findxy(A, B, a, b):
    a, b = simplify(a, b)
    z = (min(A*b, B*a) // (a*b)) * a * b
    return z // b, z // a


发表于 2021-04-29 10:44:49 回复(4)
pein531头像 pein531
要求x和y的乘积最大其实就是要x尽可能大（或y尽可能大），因为比例a/b已经固定了，y=x*b/a并没有什么操作空间。
先求取a和b的最大公约数将a/b化为最简分式，我们可以认为存在一个单元unit，使得x=a*unit，y=b*unit，因此可以得到unit1=x/a，unit2=y/b。
由x/y=a/b可知x/a=y/b，而x/a<=A/a，因此unit1<=A/a，同理unit2<=B/b，因此unit只需要同时满足不大于A/a和不大于B/b即可。又因为x要尽可能大，所以unit就要尽可能大，于是得到unit=min(A/a,B/b) 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int A = Integer.parseInt(params[0]), B = Integer.parseInt(params[1]), a = Integer.parseInt(params[2]), b = Integer.parseInt(params[3]);
        int greatestCommonDivisor = gcd(a, b);
        // 先约分
        a /= greatestCommonDivisor;
        b /= greatestCommonDivisor;
        // 然后计算unit
        int unit = Math.min(A / a, B / b);
        // x占a份unit，y占b份unit
        System.out.println(unit * a + " " + unit * b);
    }
    
    private static int gcd(int a, int b){
        if(a < b){
            int temp = a;
            a = b;
            b = temp;
        }
        while(b > 0){
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}
scala版本 
import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val row = StdIn.readLine.trim.split(" ")
        val A = row(0).toInt
        val B = row(1).toInt
        var a = row(2).toInt
        var b = row(3).toInt
        val greatestCommonDivisor = gcd(a, b);
        a /= greatestCommonDivisor;
        b /= greatestCommonDivisor;
        val unit = math.min(A / a, B / b)
        println(s"${a * unit} ${b * unit}")
    }
    
    def gcd(num1: Int, num2: Int): Int = {
        var a = num1
        var b = num2
        if(a < b){
            val temp = a
            a = b
            b = temp
        }
        while(b > 0){
            val temp = a % b
            a = b
            b = temp
        }
        a
    }
}

编辑于 2021-08-26 11:01:01 回复(0)
墨羽魂韶头像 墨羽魂韶

由于已经确定, 可以求出其最简分式为 其中为a和b的最大公约数

由于存在一个倍数使得与上式相等, 故只需要找到符合条件的最大的即可, 可通过比较和的大小得到

#include <iostream>
using namespace std;
#define int long long

int gcd(int a, int b) { return a%b?gcd(b, a%b):b; }

signed main() {
    int a, b, c ,d; cin >> a >> b >> c >> d;
    int t = gcd(c, d);
    c /= t, d /= t;
    if( a < c && b < d) {
        cout << "0 0" << endl;
        return 0;
    }
    t = min(a / c, b / d);
    cout << c*t << " " << d*t << endl;

}
发表于 2022-03-13 08:01:10 回复(0)
hello0427头像 hello0427
为什么没有人考虑a和b互素呢
发表于 2022-03-10 15:49:12 回复(0)
kyzheng头像 kyzheng
Python暴力版本，复杂度过大，供参考 
A, B, a, b = map(int, input().split())

sum1 = 0
x = 0
y = 0

for i in range(1, A+1):
    for j in range(1, B+1):
        if i/j == a/b and i*j >= sum1:
            sum1 = i*j
            x, y = i, j

print(x, y)


发表于 2022-03-19 16:32:07 回复(1)
Python
菜鸟要找工作头像 菜鸟要找工作 
def simplify(a, b):  # 欧几里得方法求最大公约数
    m, n = a, b
    while n > 0:
        m, n = n, m % n
    return a // m, b // m

A, B, a, b = map(int, input().split())
a, b = simplify(a, b)
unity = min(A // a, B // b)  # 求出最大的满足条件的unity，是的a，b乘以unity都在范围内
print(a*unity, b*unity) 

发表于 2022-03-02 23:02:22 回复(0)
jackfrank1414头像 jackfrank1414
为什么没有人考虑a小于b的情况？
发表于 2021-09-15 14:23:05 回复(0)
yyyyyen头像 yyyyyen
请问大神们 为什么不能这样写呢 没看出区别在哪 但是一个样例都过不了 求指教 
#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(b > 0) return gcd(b, a % b);
    return a;
}
int main()
{
    int A,B,a,b;
    cin>>A>>B>>a>>b;
    int num  = gcd(a, b);
    a=a/num;
    b=b/num;
    int x,y;
    int isfind=0;
    for(y=B; y>=1; y--)
    {
        if(a*y%b==0&&a*y/b<=A)
        {
            x=y*a/b;
            isfind=1;
            break;
        }
    }
    if(isfind==0)
        cout<<0<<" "<<0;
    else
        cout<<x<<" "<<y;
    return 0;
}

就是x=a*y/b，然后找满足条件的最大的x值
发表于 2022-03-23 22:24:02 回复(1)
爆爆只是想帮忙头像 爆爆只是想帮忙 
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
    if(b > 0) return gcd(b, a % b);
    return a;
}
int main(){
    int A, B, a, b;
    while(cin >> A >> B >> a >> b){
        int num  = gcd(a, b);
        a /= num;
        b /= num;
        int i = a, j = b;
        int turns = min(A / a, B / b);
        if(turns == 0) cout << "0 0" << endl;
        else cout << a * turns << " " << b * turns << endl;
    }
}
发表于 2022-03-13 10:44:26 回复(0)
Python
静音之士头像 静音之士 
def niuke2():
    A, B, a, b = [int(i) for i in input().split()]
    gcd_ab = gcd(a, b)
    x_min = a / gcd_ab
    y_min = b / gcd_ab

    mul = min(int(A / x_min), int(B / y_min))
    return str(int(x_min * mul))+' '+str(int(y_min * mul))

# 求最大公约数
def gcd(mm: int, nn: int) -> int:
    m = max(mm, nn)
    n = min(mm, nn)
    rem = 1
    while rem:
        rem = m % n
        m = n
        n = rem
    return m

print(niuke2())


发表于 2022-03-07 11:34:20 回复(0)
牛客260878540号头像 牛客260878540号

A，B都取4，a=3，b=2，此时x，y取值应该是4，4，而不是上述程序一样取3，2。


编辑于 2021-08-15 17:39:15 回复(5)
C/C++
中南大学李彬头像 中南大学李彬 
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef unsigned int u8;
ll A,B,a,b;

int MaxFactor(ll a,ll b)
{
    ll c=b;
    while(a%b!=0)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return c;
}

int main()
{
    cin>>A>>B>>a>>b;
    int MaxCom=MaxFactor(a,b);
    int simp_a=a/MaxCom,simp_b=b/MaxCom;
    int k;
    if((b*A)/(a*B)) k=B/simp_b;
    else k=A/simp_a;
    u8 x=k*simp_a;
    u8 y=k*simp_b;
    cout<<x<<" "<<y<<endl;
    return 0;
}
发表于 2021-06-01 16:15:45 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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