蓝桥杯192.等差数列java

使得等差数列最短就是让已知的项数最大的作为末项，最小的作为首项，根据a1+(n-1)d=an可以知道我们需要找出最大的d即可，将已知的数列排序后的相邻两项的差为：差1=a*d，差2=b*d，差2=c*d，差3=e*d，差4=f*d（a,b,c,e,f...为正整数可以相等）。。。。所以d就是这些差的最大公约数，即可求出最短的项数

import java.util.Scanner; import java.util.Arrays; // 类名必须为Main public class Main { // 求两个数的最大公约数（辗转相除法） private static long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); long[] num = new long[n]; // 用long避免溢出（Ai可达1e9，差可达1e9，GCD计算安全） for (int i = 0; i < n; i++) { num[i] = in.nextLong(); } Arrays.sort(num); // 特殊情况：所有元素都相同，直接输出n（最短就是n项，公差0） if (num[0] == num[n - 1]) { System.out.println(n); return; } // 计算所有相邻差的最大公约数，作为公差 long d = 0; for (int i = 1; i < n; i++) { long diff = num[i] - num[i - 1]; d = gcd(d, diff); } // 计算项数：(末项 - 首项) / 公差 + 1 long ans = (num[n - 1] - num[0]) / d + 1; System.out.println(ans); } }