[数据结构与算法]【编程练习】比例问题

题目来源：牛客，阿里巴巴编程题（2星），第4题

题目描述

题解

思想：先化简a/b至俩质数之比。那么，x/y = a/b*m。又因为x和y需要小于A和B，且x和y的乘积最大。这意味着m需要满足：x和y是小于A和B的最大值。这里，m存在两种可能性：
1）x是小于A的最大值：m1=int(A/a)，x1=m1a，y1=m1b；
2）y是小于B的最大值：m2=int(B/b)，x2=m2a，y2=m2b；
现在就需要判断，应该选取m1还是m2:
当y1大于等于B时，m1被排除；当x2大于等于A时，m2被排除；
当m1和m2同时满足时，选取x和y乘积最大的那一对。
上代码：

# 先求a和b的最大公因数，使得a和b能化简到最小质数之比
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

def main():
    global gcd
    A,B,a,b = map(int,input().split())
    gcdt = gcd(a,b) # gcdt是a和b的最大公因数
    a,b = a/gcdt,b/gcdt # 更新a和b
    mlta,mltb = int(A/a),int(B/b) # m1和m2
    mlta = 0 if mlta*b>B else mlta # 判断m1是否满足条件，不满足则设为0
    mltb = 0 if mltb*a>A else mltb # 判断m2是否满足条件，不满足则设为0
    xa,ya = mlta*a,mlta*b # 计算x1和y1
    xb,yb = mltb*a,mltb*b # 计算x2和y2
    # 看谁的乘积大就输出谁
    if xa*ya>xb*yb:
        print(int(xa),int(ya))
    else:
        print(int(xb),int(yb))
    return

if __name__=='__main__':
    main()

小总结

最大公因子的计算方法：辗转相除法

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

证明：
设c=gcd(a,b)，则a%c=0; b%c=0;
则(xa+yb)%c=0;
设a=mb+n，则a-mb=n；
所以，令x=1，y=-m，则(a-mb)%c=n%c=0；
所以gcd(a,b)=gcd(b,a%b)