公约数例题——等差数列、最大比例_综合

1246. 等差数列

数学老师给小明出了一道等差数列求和的题目。

但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式
输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,???,AN。(注意 A1?AN 并不一定是按等差数
列中的顺序给出)

输出格式
输出一个整数表示答案。

数据范围
2≤N≤100000,
0≤Ai≤109
输入样例：
5
2 6 4 10 20
输出样例：
10
样例解释
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。
首项为a，公差为d
a a+d a+2d a+3d a+kd …
所有项与第一项的差肯定是d的倍数
d最大，最大公约数

IA = lambda:map(int, input().split())n = int(input())
a = list(IA())a = sorted(a)
# 首项为a，公差为d
# a a+d a+2d a+3d a+kd ......
# 所有项与第一项的差肯定是d的倍数
# d最大，最大公约数
def gcd(a, b):if b!=0:return gcd(b, a%b)return amin_d = 1e9
x = a[1] -a[0]
for i in range(2, n):x = gcd(a[i] - a[0], x)min_d = min(min_d, a[i] - a[i-1])if min_d == 0:print(n)
else:print((a[n-1]-a[0])//x+1)

1223. 最大比例

X星球的某个大奖赛设了 M 级奖励。

每个级别的奖金是一个正整数。

并且，相邻的两个级别间的比例是个固定值。

也就是说：所有级别的奖金数构成了一个等比数列。

比如：16,24,36,54，其等比值为：3/2。

现在，我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。

输入格式
第一行为数字 N ，表示接下的一行包含 N 个正整数。

第二行 N 个正整数 Xi，用空格分开，每个整数表示调查到的某人的奖金数额。

输出格式
一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。

数据范围
0<N<100
0<Xi<1012
数据保证一定有解。

输入样例1：
3
1250 200 32
输出样例1：
25/4
输入样例2：
4
3125 32 32 200
输出样例2：
5/2
输入样例3：
3
549755813888 524288 2
输出样例3：
4/1

题解
假设原数列为 $a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^{(n-1)}$
假设抽取的数列 b0,b1,…,b(N-1) (从小到大排好序了)
$b 1 / b 0, b 2 / b 0, . . ., b (N ? 1) / b 0$
= $p/q)^{x1},(p/q)^{x2},...,(p/q)^{x(N-1)}$
我们要求的是： $p/q)^k \ \ \ (p/q)>1$ ,所以使k最大，即求 $p/q）^{x1} -(p/q)^{x(N-1)}$ 的最大公约数，其实就是求x1~x(N-1)的最大公约数
这里我们使用更相减损术，因为我们没有得到确切的x1~x(N-1)是多少，我们只有 $p/q)^{x1},(p/q)^{x2},...,(p/q)^{x(N-1)}$ 这些的值，用辗转相减法，分子分母分开求。具体证明可以看下面。
最后 $f(p^x,p^y)$ 为求x,y的最大公约数，但返回的结果为p^gcd(x,y)
辗转相除法 o(logn) (a,b) = (b,a%b)
辗转相减法 o(n) (a,b) = (b,a-b)

用辗转相减法原因：
两个指数相减可以转化为相除
两个指数相除开根号

辗转相减法介绍
时间复杂度：o(n)
gcd(a,b) = gcd(b,a-b)
主要应用：
辗转相减法可以用来求若干个形如 $\frac{p}{q})^{r_{i}}$ 数的求 ${r_{i}}$ 最大公约数d,分子分母分开求，即返回结果为 ${p}^{d}$ 或 ${q}^{d}$ :

算法推导
$f\left(p^{x}, p^{y}\right)=p^{(x, y)}=p^{(y, x-y)}=f\left(p^{y}, p^{(x-y)}\right)=f\left(p^{y}, \frac{p^{x}}{p^{y}}\right)$

int gcd_sub(int a, int b){if(a < b) swap(a, b);if(b == 1) return a; // 此时p^y = 1即y = 0// 由于0和任何正整数r的最大公约数都是r，所以此时应返回p^r，即areturn gcd_sub(b, a / b);
}

本题代码

IA = lambda: map(int, input().split())x = list(IA())
n = x[0]
if len(x)>1:a = x[1:]
else:a = list(IA())
a.sort()
def gcd(a, b):if b:return gcd(b, a%b)return adef gcd_sub(a, b):if a < b:a, b = b, aif b == 1:return areturn gcd_sub(b, a//b)res = []
for i in range(1, n):t = gcd(a[0], a[i])res.append([a[i]//t, a[0]//t])res1 = res[0][0]
res2 = res[0][1]
for it in res:res1 = gcd_sub(it[0], res1)res2 = gcd_sub(it[1], res2)t = gcd(res1, res2)
res1 //= t
res2 //= t
print(str(res1) + "/" + str(res2))