第十届2019年蓝桥杯真题
AcWing 1246. 等差数列
C++B组第8题
最大公约数
欧几里得算法
在等差数列中,每一项与第一项的差一定是公差d
的倍数,但是题中的等差数列有一部分未连续,所以我们要找到除了第一项,其余的每一项和第一项的差的最大公约数d
,d
就是整个数列公差的最大值。
求项数公式:$a_{末}-a_{首} \over d$ $+ 1$
时间复杂度
$O(NlogN)$
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static final int N = 100010;
static int[] a = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
Arrays.sort(a, 0, n);
int d = 0;
for (int i = 1; i < n; i++) d = gcd(d, a[i] - a[0]); // 求最大公约数
if (d == 0) System.out.print(n); // 表示所有项都相同
else System.out.print((a[n - 1] - a[0]) / d + 1); // 求项数公式
}
private static int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
}
厉害呀