蓝桥杯192.等差数列java

使得等差数列最短就是让已知的项数最大的作为末项最小的作为首项根据a1(n-1)dan可以知道我们需要找出最大的d即可将已知的数列排序后的相邻两项的差为差1a*d差2b*d差2c*d差3e*d差4f*da,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差可达1e9GCD计算安全 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); } }