摘要
Title: 1223. 最大比例
Tag: 辗转相减法、gcd
Memory Limit: 64 MB
Time Limit: 1000 ms

1223. 最大比例

题意

X星球的某个大奖赛设了 M 级奖励。
每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。
比如：16,24,36,54，其等比值为：3/2。
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
思路

先对数组进行排序和去重，其次对于相邻的两个数来说，先求他们的gcd，再把他们整除gcd的结果记录，即是分子和分母
接下来就是在这 $n - 1$ 个 $(\frac{p}{q}) ^ k$ ，求 $\frac{p}{q}$

辗转相减法：
1
2
3
def gcd2(a, b):
if a < b: a, b = b, a #需保证a是大于b的，不然会出现负数
return gcd2(b, a - b) if b else a
给出结论：

变成除之后的b的判断条件，变成了 $b=1$

代码

'''
Author: NEFU AB-IN
Date: 2022-04-01 17:33:21
FilePath: \ACM\Acwing\1223.py
LastEditTime: 2022-04-01 17:33:21
'''


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


def gcd_sub(a, b):
    if a < b:
        a, b = b, a
    if b == 1: return a
    return gcd_sub(b, a // b)


fz, fm = [], []
n = int(input())
a = list(map(int, input().split()))

a = sorted(list(set(a)))

for i in range(1, len(a)):
    d = gcd(a[i - 1], a[i])
    fz.append(a[i] // d)
    fm.append(a[i - 1] // d)

up, down = fz[0], fm[0]
for i in range(1, len(fz)):
    up = gcd_sub(up, fz[i])
    down = gcd_sub(down, fm[i])

print(f"{up}/{down}")

1223. 最大比例

题意

思路

代码