题目
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。
输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
思路
我们设原序列是{ x, xq^1, xq^2, ..., xq^n−1}，从中挑出一些数字 {xq^c, xq^d, ..., xq^y, xq^z},计算他们对于第一个数的比值，得到{1, q^{d-c}, ... , q^{y-c} , q^{z-c}= {1, q^{kd}, ... , q^{ky} , q^{kz}}，让q=a/b,那么这个序列就变成了{1, （a/b）^{kd}, ... , （a/b）^{ky} , （a/b）^{kz}}，a和b可以由(xq^i//最大公约数)和（xq^c//最大公约数）求得，即对xq^i，xq^c约分。这样我们就得到了A，B两个序列A={ a^{kd}, ..., a^{ky}, a^{kz} }, B=B={ b^{kd}, ..., b^{ky}, b^{kz}}，问题就转化为已知A，B两个序列，求a和b
对于数列A，B我们通过辗转相除的方法求得最终的a和b的值
代码
1. # 请在此输入您的代码 2. from math import gcd 3. 4. def gcd_sub(a,b): 5. if a<b: a,b=b,a 6. if b==1: return a 7. return gcd_sub(b, a//b) 8. 9. 10. n=int(input()) 11. s=list(set(map(int,input().split()))) 12. 13. s.sort() 14. n=len(s) 15. a,b=[],[] 16. for i in range(n): 17. d=gcd(s[0], s[i]) 18. a.append(s[i]//d) 19. b.append(s[0]//d) 20. 21. up=a[0] 22. down=b[0] 23. n=len(a) 24. for i in range(n): 25. up=gcd_sub(up, a[i]) 26. down=gcd_sub(down, b[i]) 27. print('%d/%d'%(up,down))
