题解 | #比例问题#

算法思路

1. 先用辗转相除法求a与b的最大公约数，将a与b的比例化至最简，
2. 然后在A->a与B->b中选择缩小的倍数最小的，该倍数乘以a和b即为答案

时间复杂度分析

• 该算法的时间复杂度为欧几里得算法的时间复杂度，为O(lg min(a,b))，是对数级别的

实现代码

#include <iostream>
using namespace std;

/**
 * 牛客 比例问题
 * 运行时间 4ms 占用内存432KB
 * */

int get_greatest_common_divisor(int a,int b){
    if(a<b) swap(a,b);
    do{
        int remainder=a%b;
        a=b;
        b=remainder;
    }while(b);
    return a;
}

int main(){
    int A,B,a,b; cin>>A>>B>>a>>b;

    int &&divisor=get_greatest_common_divisor(a,b);//获取最大公约数
    a/=divisor;//将比例化至最简
    b/=divisor;

    double su1=A*1.0/a;//缩小倍数1
    double su2=B*1.0/b;//缩小倍数2

    int times=su1>su2?(int)su2:(int)su1;//选择最小的那个作为倍数

    cout<<a*times<<" "<<b*times<<endl;//答案

    return EXIT_SUCCESS;
}